CMU Database Group · 1:23:19 · https://www.youtube.com/watch?v=HNtlew7mCc4
0:05 official members bounce bust off the Chrome realize it's real hell what we call Home official members bounce bust off the Chrome realize it's real hell where we from the ins side one I Vision fat lcks and M Clips the Chrome will make the average imitator do back flips you like a [Music]
0:27 pistol I you s to say this every year man like it's almost November it should not be 75 degrees um but it is what it is go register vote outside I can't vote this year but if you can please go register okay um administrative stuff project two again is due uh this coming up this Sunday who here has not started project 2 excellent fantastic okay of course the people that are in the lecture probably haven't started all right so we having our Saturday office hours um again this Saturday the day before it's due between 3 and 5 we'll announce this on on Piaza
1:04 it'll be in in the same location any questions comments or concerns about project two yeah yes but again we gave you guys the test for that reason that like we gave you all the tests for everything ahead ahead of time uh so you can debug
1:20 locally all right homework two will be out this Wednesday and that'll be due in two weeks on November 3rd and then midterm exam grades uh almost all of them are graded few few people had to take take up the make makeup exam on the weekend uh so those we need to get graded and hopefully we'll post those on pza tomorrow okay and I think the mid semester grades are due Wednesday is but that's on me not you guys all right uh the other things that that are happening
1:47 uh again we have a lot more speakers this uh the semester now the fall break is over uh so today we have spice. a there is a spice DB that's different from These Guys these are spiced AI okay uh and so they're basically using duct DB data Fusion I think SQL light and everything all ones doing AI right so we'll figure what that means and then the Exon guy is coming to give it a talk be on Zoom next week uh let's see whether he changes the the name of the system by then and then Sonata is a streaming system and they'll be also using data fusion and they'll be g a call in three weeks okay again these are all optional all right so right before the fall break and in the midterm
2:27 we were discussing joins right and then prior to that we talked about how how to do sorts how to do uh aggregations right these the fundamental building blocks of of the of the operators you would need to have in a relational database system
2:41 so now the question is okay so I know how to implement individual operators how do I put this all together and run a real query and that's what today and next class will be all about So today we're going to be talking about what how you actually want to build the system to define or specify how we're going to move data between the these operators uh when we actually want to execute queries what does the output look like how do we handle insert update and deletes right
3:08 so when when a database system relational datab system is given a SQL query it's going to convert it into a a query plan and ideally you want the quer plan to be a directed A like graph a dag most systems Implement Implement them as trees we can discuss a little bit as we go along why dags preferable but basically if it's a tree you can't reuse output very easily without do some trickery right but Simplicity say we're doing joint here join an RNs right the the query plan tree is going to look roughly like this at the leaf nodes we we're doing the scans in
3:42 RNs then the r feeds into the the build side of this join uh ass a hash join it actually doesn't matter the S feeds into the filter operator does the join and then produces the output we do we do a projection right so this again this is the logical plan I didn't specify you know I said is probably a has Jo but it doesn't matter like RNs doesn't not specifying how what algorithm we're using to access this data and that's what sort of today's class and next class will be about what are these
4:10 operator implementation Direction going to do and how they're going to move data between the operators and then next week we'll pick we'll talk about quer optimization how do we decide of the choices we would have for different operator implementations which which one we actually want to
4:22 use right so this is pretty easy to understand right sort of data is Flowing uh logically because we'll describe physically How We Do It second but data is Flowing logically from the scan on R into the joint or scan on S into the filter
4:36 operator but now we can Define boundaries within this logical plan called pipelines and a pipeline is going to be a sequence of operators where the the data can move continuously from one oper to the next without having to block or wait for more data to be processed so what do I mean by that so in this say we have this first pipeline here on r i can scan R and assuming it encompasses the say this is again the hash joint a build side I can scan R and feed into the build side of of the join
5:10 here but then at that point the pipeline is done right because I can't do anything else for all the data I just came just came out R because now I got to do the probe I got to do the joint the the the probe side of the joint so the pipeline breaker is essentially the boundary the end point says I can't continue up with this any Tuple in this pipeline until I run something else in my query plan another another
5:33 pipeline so in pipeline two assuming again we we ask you pipeline one first we do the scan on R and now any Tu coming at sorry scan on S any Tu coming at at s we can ride all the way up to the top to produce our output right assuming we've already run pipeline one so I scan a two on S I do my filter I do my probe into my my join say the join predicate gets satisfied the TU keeps going up then I do my projection and then it's output it
6:00 right again the idea of a pipeline is basically that it's it's the the boundary which we can execute a bunch of operators uh without having to go materialize them into intermediate storage like have potentially a buffer that we have to spill a
6:14 desk and then a pipeline breaker is going be anything where we can't keep continuing until we uh or can't execute anything else until we get more until we get all the tuples uh below us right this would be obviously we're join on the build side if we take subquery nested queries that we don't decorrelate them correctly right we got to execute the entire sub nested query then as a pipeline then we ex another pipeline or like an order by Clause is kind of obvious you can't produce any output of an order by operator ignoring even Heap scan you can't do this yeah you can't produce any output of a of a order by operator sorting operator until you sort everything because you don't know what the ranking the ordering is going to
6:50 be right so this is the high L model that we're going to work with and then the question we're going talk about today is what are these lines right I'm saying they're logical because saying logical logically data goes from R into the join but what are we actually sending and who's actually invoking us to send it so that's what today's lecture is about to execute the queries so we first talk about how to do processing models again this would be just how we're going to execute these queries and move data from one oper to the next then we talk about the access methods we've already discussed these in some ways like how to do index games for but that's the lower portions of the of the query plan where data is coming out of Base tables but it doesn't necessarily have to be then we'll talk about how how to handle queries that modified database and then finish up we talk about how we actually evaluate the predicates in our wear Clauses and our join Clauses like a equals 1 how are we actually going to execute
7:40 that okay all right so a processing model defines how a database system is going to execute a query plan and how it's going to move data from one operator to the next and just like before when we talked about row stores versus column stores there's going to be tradeoffs in our system design that will be preferable for a o2p workloads a rastore essentially and preferable for a column store right in an analytical
8:11 workload and then as we Define our processing model within our system we're going to have two mechanisms to to uh I'm use control because there's a control flow but there's basically two mechanisms for how the D is going to coordinate the execution of these operators and producing output or output tuples and then where it's going to go so you're going to have the control flow is the mechanism for how the DAT syst is going to say okay you're the you're next operator I want to run go ahead and run produce your output could or could be a pipeline or a series of operators and then the data flow is going to be where and how the operator is going to send its
8:47 results and we'll see in one case in the iterator model they're actually going to uh blur the lines between the two of these because the way they're going to say I have enough data stop running me is the same way you know tell stop running at
9:01 all right and as we see as we go along the output of an operator will depend on what processing model we want to use and it could be either the the tire entire tupal could be the subset of the tupal
9:14 if it's column store and it can be one Tuple all the tup or some of the tup like I said there's and there's trade-offs for for all of these so the three approaches going to be the iterator model materialization model and vectorized model and the high of idea is that the iterator model is the most common one it's what what people implemented when they first started building a systems and just going to be moving two plus one at a time and then the materialization model be all the tupal come out of an operator
9:39 and then the vectorized batch model is sort of hybrid between the two of them and so the way to think about them is the mo the most the that you know about right the postes the myal the oracles the db2s all those the mongos most of them are going to be using the iterator model to send one two at a time uh the materialization model is is very rare there's probably five systems in the world that I know of that do it and then the the vectorized model is more common
10:07 in the last 10 years because this is what all the olap systems are going to do this is what your snowflakes and and your data bricks and so forth are going to do okay all right so go we'll talk about the advantag and disadvantages of each of these one by one um and then there's a second design decision we'll talk about afterwards is like are we moving the data from the top to the bottom or from the bottom to the top but that's orthogonal to uh the process model right now we'll cover that
10:32 afterwards all right so the iterator model is the most basic one and again this is the most common implementation that that uh most especially in row store systems that that they're going to use and so each operator in your query plan is going to have to find this or implement this API that that provided
10:49 from the system that's going to have basically three functions there's a next function that says all right give me the next Tuple uh that that you that the operator produces the next tupo that's that's be part of the output uh of the data that's processing and the idea is that the parents going to keep calling next over and over and over again on their child child operator I keep getting more and tupal and at some point the child operator says okay I don't have any more tupal for you and it sends back a a null pointer or and a file marker to say okay there's no more tubal
11:20 for you from coming from me never call me come call next on me again all right and then what's going to happen happen is because we just have this sort of simplistic API which is calling next now we can compose these operators uh together such that if I'm some operator and I have a child I don't care how that child is actually producing data I just know I got to call next on it so I don't care whether it's coming from Over the network or coming from an index or coming from a cenal scan on a local file
11:49 or it's actually a subquery right it doesn't matter I can inter I can intermix these operators uh and and and everything just sort of works together nicely there's some EXT metadata we can maintain about the state of of of a of an operator so we have to have open and close functions right so think of like when you call open uh on an index scan operator that's like creating the the iterator for your your B+ Tre that you instantiate the iterator you move it produce one Tuple and then when you call next again you just move the iterator over by one and get the next
12:22 Tuple right and then when when when you reach the end of the of the scan uh you return back and a file and then the Clos function will you can go ahead and clean up the iterator right so I said this approach is used in most Data Systems you'll see these sometimes called uh the volcano model because there was a guy uh the guy who heard that book on the B+ Stree that we talked about before he had a very famous paper on a query Optimizer and a processing model called the volcano model where he described how to do this
12:52 uh to extend the iterator model to do parallel queries we'll see that next class um or it's also something as the pipeline model because again the idea within you call next uh going down in a pipeline and just ride the tube will rise all the way up to the top
13:07 right all right so look at the high level diagram uh so we have a simple joint on RNs and then we we have our predicate uh on s.v value greater than 100 so I normally don't like to show code uh but I think this is pretty simple for you guys to understand so you can think of like each operator implementation is going to be essentially a for Loop over some data source that they're getting from so the bottom guy on the scan scan on R right it's getting every single t on R but the ones up above they're they're getting tupos from their from their children so you can think of the all these functions like these are like the next calls that all the operators are going to evoke uh on each
13:44 other so when I start off right you start at the root of the query plan and so you have this first query plan up here and you call some some you know the datab system calls next on this function and inside that we see we have a for Loop we're going to get every single tupal from the its from its child the next function from its child so this will be a blocking call so when this the first guy at the top calls child. next
14:07 there's a blocking call that then jumps down to the the operator below it and its next function implementation says okay well now I want to start scanning data to start producing output to my parent well the first thing it has to do is go build the hash table because this is going to be doing a hash join so again so we first thing we do is we do a scan uh for every single Tuple on the left Child Called next right and then as this thing gets evoked down here then then jumps down here and then now we do the scan on R and then for every single Tuple in R we call emit it's almost like a yield function if you written like a python dat rator uh and then the data goes up uh as a single Tuple goes up to
14:45 the the parent and the joint operator who then inserts it into the hash table and then it Loops back around and calls next again on its child and get until you know keeps going to get all the tupos and then at some point it's done says I don't have any more tupos for you and doesn't evoke it anymore because now the hash table has been
15:03 built then now we drop down to the uh to to the right side of the joint and again this is still from one call and next from the root root node one call and next says okay I can't emit any Ts for you until I first build my my my my hash table so I got to go iterate on on R until you run out of TS here then I'm now going to come down the other side it calls get next on on the the filter operator which calls get next on the on it on it child which is the scan on on S
15:33 and it keeps producing two BS up one by one which then bubbles up if they pass the filter up to the the the joint operator and then now I can do a probe in my hash table and then if that there's a match then I produce a tupo at the top up
15:52 there pretty straight for it right so again thinking in terms of terms pipelines pipeline number one is the scan on R and I'm really easy way to show this but like it's the and the build side of the join so it's this operator here to scan R and then the first Port part of the of the joint operator when I build a hash table right and again the pipeline breaker is that I can't I can't produce any output for my child up above because I still have to go on the on the on the the right side and call the right child
16:24 question for each next at the second level why is it that we go through enre table here so question is if you're going back here why why do I have to go call left. next get every single tupon R before I get on the right
16:43 side uh like for each call next We're looping through the entire table no no yeah sorry think of this like as a this is an iterator like like so I call get next and then then when I call admit there's like a the I'm returning control but when I call next again I'm picking up where I left off okay right I didn't want to show like again it's pseudo code wasn't trying to show that yeah it's it's for one get next I only get one Tuple yep but now again the the I'm trying to think there are there are any situations where you would you could do that but like the the thing up above the parent doesn't need to know what how this thing's actually implemented so for say for some reason it did have to scan everything all over again it's still only going to produce one
17:27 tupal uh but that you know the thing above doesn't know doesn't doesn't care also which you could happen which we'll see in in a second in the materialization model but like if I really wanted to say somehow like scanning R is really expensive to keep sort of doing it like peace meal so I could just scan all of R produce some some buffers intermediate results and then every single time I call get next on this it produces one from that buffer but again up above I don't know know whether that happened or not I don't
18:03 care okay so as I said this this approach is pretty much used in almost every single data system that's out there it's the easiest thing to implement this is what busb uses uh it's easy to debug because you just walk through the code uh and see all the function calls and and then see how you know things things Break um and again speaking from experience and speaking from students working a bus for years another nice advantage to this is that the the output control is really easy with this approach because if I have a limit claws up above like give me the last give me the top 10 tupal or
18:37 give me 10 only 10 tuples the way I I Implement that is I just stop calling get next after I got 10 things right so this is what I've say where like the control flow and the data flow uh logic or path are sort of inter intermixed right there isn't a way to say hey go stop like going back here I don't have an easy way if this is scanning I don't have an easy way for someone else to come in and say hey stop scanning kill this query stop st what you're doing right because that that you've already the stack has gone down
19:08 uh and You' recursed into the query plan and it's doing whatever it wants to do and you have to have sort of a side Channel method to kill it one question yes you go back one slide yes why are there two pipelines instead of one question why are there two pipelines instead of one uh so again I scan R again think of like the build side of this as part of the first pipeline I scan R build the hash joint right build the hash table for the joint I can't produce any tups as the output until I build that hash
19:38 table right because what would happen if if if this thing was running and then I I have a th000 tues but I insert aund of them and I keep trying to put the rest in and then I start running this guy over here now when I do a probe in that hash table I may end a false negative because the tup that I would match just hasn't been inserted yet so so the data system knows that the dependencies
19:57 between the pipelines and and say okay this first pipeline can run and second pipeline cannot run until this one finishes Okay and like I said pretty much every single data system you can think of uh for the most part anything that's a row store will be doing something like
20:15 this all right the alternative model is the materialization model and this is there is still a sort of a next function but it really is like give me everything so instead of producing one Tuple uh anytime you invoke down the operator you get all the tupal from that operator and then at which point you never go back and ask it for more data because you have everything that you could ever ever possibly
20:39 need right and again you would you you could have it produce either a single uh sorry the all the tupal or sorry all the attributes or columns for the tupal or are subset of them obviously if I have a one you know one petabyte
20:54 table uh I want to try to push down as much as I can into the scan operator because I don't want to just passing wrong one one paby of data when maybe I only need a small portion of it so this is a um this this technique was developed in the 1990s out of this uh project called monb uh I think I might have mentioned many before um came out of the CW School in Amsterdam um and the first version of duck DB was actually an better version of mon ver yeah the first version of duck DB was called monb light because it was like an embedded version of MB they threw all the code away and then rewrote it based on what the the Germans do um
21:34 but it's it's it's from the same school all right so again I don't want to show code but because I have to so now instead of having a single next function uh and producing like through an iterator model you emit tupal output as as output now there's a return Clause that says okay here's my output buffer at all the tupal that I'm going to need for this operator into that up buff and then return it back so just like before I'm going to start from the bottom the the the rout calls child. output calls down into here again now we're doing a hash joint I got to call left. output that jumps down to here now this scan operator is can produce all the tupal
22:08 from R into this buffer that gets passed up into the here and then now I can build my hash table and then I come down on this side of the of of the the query plan or the pipeline uh and then do the same thing scan s produce the output pass it into this operator who then passes up to that operator
22:28 you think it's a good idea or a bad idea I've sort of said before why it's a bad idea I just take this example right here right so what am I doing I'm taking all the tupal in s adding to an output buffer and then now passing to this operator who's just going to scan through and apply the predicate again always think of the streams I have a they have a billion tupal but my predicate is only to match two of them
22:54 that sucks right because I just passed a billion tuples to only you know throw away 99.9% of them so a really simple optimization you can do in in this world is what's called operator Fusion where the idea is basically inline or combine different operators uh that that are within the same pipeline where you know that you don't need to have that sort excess copying so in this case here this says scanning the the output of this guy and applying the predicate well I can just do that all all together once right scan R then apply the predicate if it matches
23:27 put it put them to my Alpha buffer so you can do this for projections you can do this for uh uh filters uh not not not you can't do it for everything um you can do it for limits if you know you don't have an order bu up above
23:44 right and then just like before the pipeline breaker would be I can't can't you know keep riding TS up um I really really do pipeline wouldn't do pipeline in material model but you know I can't can't produce an of this operator here until I I first build build my hash table and then do the Probe on the
24:07 join so monb started off as an olap system uh originally designed as an oap system and it was one of the first column stor systems um and it was meant to be idea of like processing entire arrays of of of of of of entire Columns of tubal um and that's sort of why they thought it would be good to have this materialization model
24:29 it's only really useful in the oldp world um because in that world the queries are only accessing a small number of tobes at a time so yeah you're going to materialize the entire output of the of of the of the operator all at once
24:45 but if you do that then you never have to go back and get more data so if you call like think of the get next in the iterator model I say my operat produce one Tuple I call get next it gives me one tupal I call get next again and then it comes back and says okay end a
25:01 file right those function calls actually add up especially if your database is in memory and your queries are really really fast like because it's a jump call in in in in in the CPU so if you now if you have sort of designed the like an array like I know I this thing is going to call this it's going to call this and you actually don't even have any indirection to figure out what what needs to call what
25:24 you just going to rip through that array and call these operators produce their output and pass it one the and it's much faster but you can only really do this for OTP um because the output coming out of one operator is going be small so this is actually what we implemented in in hore over 15 years ago which then got put into the commercial version of vol DB um and then crate DB is out of Europe Raven DB is a document store based on um
25:53 similar to similar like mongodb these systems use it uh but MB and Hy mon highrise where the olap system is trying to do this mon still does it highrise got rid of it and switched to the the next thing we'll talk on the next slide so again good for OTP bad for
26:11 olap but we kind of we need something in in between right we know that if we're for olap something call get next it's be expensive because I have to scan a billion t i I don't want to call get next a million times but then I don't want to materialize everything all at once because again I want to be able to break things up and paralyze it and not worry about you know using up all my memory Just Produce the intermate output
26:32 of a of a of an operator so the obvious fixes do something in between it seems obvious now but again this this has only existed since 2006 2007 um because people are either doing materialization model or the or the iterator
26:49 model so vectorization model is is basically like the the iterator model but instead when you call get next instead of getting one tubal you get a batch of tbbl right think of like something like 1024 like a th th tup or something like
27:04 that and then the now you're giving it back a batch of tuples and now the the operator that got that batch of tuples will process on them that entire batch before it goes back and gets the next one or produces the output up above
27:19 right so we'll see this a second there's a bunch of tricks you can do now because you know you're processing on a a batch of tupal that you couldn't really do easily if it was a single tle again ignoring you can do all these tricks again if it's if it's if you have all the tups but then becomes almost too big
27:35 like for example if you know that all of the tupal for you know for a given attribute within a column are coming back with the exact same value like you know integer ID equals one then instead of storing that entire Vector of one one one one one over again you can have a constant Vector that says I it's like run length and coding I have the value one a thousand times now the thing you're passing around is super small
27:57 like Duck does this underneath the covers when you're running queries tries to figure out do I do I have constant values and Rees them you can compress the the data as it comes across like do doing Delta coding and other things that we talked about before because now you have a a column of data columnar
28:11 data right so going back to our example four again this is with these this sort of like the iterator model but instead of now passing a single Tuple we're passing back a vector so just like before we call get next go down the this side of the pipeline right and then now we have an output buffer that we filling up and then when our output buffer exceeds uh some size then we produce it as an output I'm not showing extra code you need to have outside the for Loop if you have like the buffer wasn't completely full since the last time you iterated
28:41 right you send whatever remaining amount you have goes up as well again so this stands back a tu batch and everything just works just like before appreciate for all right so as I said this thing has only existed since 2006 [Music]
29:01 2007 um the original paper was was a project called based on monb called monb X100 they tried using monb to do to run on Modern CPUs and they realized here's all the parts that are super slow and one of them was the materialization model so they they forked the code uh and built a sort of a high performance system that's based on the vectorization model like nowadays it sucks because you say if you goog like vectorization mod model or vectorization database you're going to find all the vector DB stuff uh you may also find bu of simd stuff which we'll talk about next class uh and that's completely independent of this
29:38 right this is just saying I'm passing back uh you know when I call my operator they're getting back a vector tubles or Bas tues so as I said every pretty much every olap system that that has come out in the last 15 years even the old ones have been retrofitted to now follow follow this approach right because the advantages especially on on Modern CPUs are pretty significant ific because now you have these kernels that are iterating uh over B the same thing over and over again and that's exactly what modern CPUs want right they don't like IND Direction they don't like doing you know some running these instructions then these other instructions and these other instruction if you can say here's a here's a stride of memory of data do the exact same thing a thousand times
30:18 CPUs love that that's the best thing to get you know get that you'll get the best performance C of this right so again if you're building ol today you pretty much want to use this this approach all right so again we talked about the three processing models iterator model materialization model vectorization model if you're building a a row store system you want to use iterator model if you're using a an olap system you want the vectorization model
30:45 materialization model again it's it's it's pretty rare if you really care about performance ltp you could do something like that so in all my examples that I showed just now uh we we the way the query was actually executed is that we started at the root of the query plan and we call get next on the root which then percolated down called get next on his children right and the essentially what we're doing in that world is we're starting from the top and we're pulling data up from the leaves to to the top to produce our
31:18 output this is how most databas system are going to be implemented but it's not the only way so that approach would be called the the the pull approach the pull Direction right top to bottom again always start with a root and you pull data up from from its children
31:35 right the alternative is to start at the bottom the leaf nodes of the query plan have them execute and then push data up to their parents right conceptually they sort of the same but the the when you start doing uh when you start fusing in The Operators of we talked about before you can do some crazy tricks and be very very efficient if you know you're doing a push page model where you're not going to be calling get next on something else right because again that's IND Direction the CPU and in some systems in the case of hyper uh I should also put um here um is the other one that CED DB does this as well but not only are they trying to keep data in CPU caches they're trying to keep data in CPU registers which is the fastest member you can have and I know said we weren't going to talk about low level Hardware below you know CPU
32:25 caches but they can get insane performance because now for one tuo I can ride it up a pipeline as far as I can and just sit in CPU registers uh and that's going to be the fastest memory you can have to execute
32:37 things so let me show what the push base model looks like so right we're going to have two pipelines like before and so in the first pipeline here it just looks like what we had before where now we're going to scan R but instead of calling emit or producing some output that we then pass to another operator right it's just going to scan R and build a hash table it's just this for Loop
33:00 here then now the second pipeline now we're going to do that Fusion we saw before we're going to scan s and immediately evaluate the predicate and then if it does Pro the hash table and then admit it if it does as part of our
33:12 projection so the thing now is going to be different than the push Bas model and the pull base model is now we don't have this get next thing that's tickling the operators and telling them okay it's your turn to run produce me some output we now need a sort of coordinator schedule that sits above all this which then now makes explicit invocations to these operators say okay it's your turn to run right go ahead and go this thing runs to uh completion and then it's going to be no it's sort of be set up ahead of time because that's part of the query plan we would generate it's going to know okay the hash table is generating is going to go at some
33:47 location in in memory in the buffer pool or or whatever and then now once this thing is completed it says schedu okay I know pipeline one is done now it's time pipeline 2 and it's already baked in or you're passing in here's where the inate results of the hashtable you cared about that was created by the first pipeline here's where to go find it now it can can just run to completion produce this output like
34:11 that again so you can do this sort of operator Fusion in in the different models uh and I'm not really showing here you know in this case here it's it's it's a the four Loop is operating on a single tupal but it could be operating on a vector tupal right you can inter you can you can mix and match these different processing models and the processing Direction uh based on you know based on what the the workload you're trying to
34:37 support so the top to bottom approach like I said is the most common one uh it's easier to control the the the output uh like how many tobes you want because you just tell okay stop calling next right and you don't need any explicit mechanisms in The Operators themselves to say okay you I've got enough data stop
34:58 the parents are you know they keep calling get next that's going to have an overhead of course because you know especially if you implement this C++ when when now you got you know you basically have an operator uh interface and then you have to look up the virtual function table C++ to say okay what actually implementation do I have um and then as we said before the CPU cost of this can be actually kind of high now again if you have to go to spill a disc and read something disc who cares about your your branch call your jump call in your CPU but if you in a well tuned system you try to keep much as memory as you can you this can start to matter a
35:31 lot the bottom to the top approach the push approach is is rare uh but you can have really tight control of where data is actually being placed again in caches in reg in registers um you do need to have additional mechanisms to say okay I got enough data stop
35:49 running uh like you basically have to embed somehow in that in those sort of nested full Loops that I show before a way to say okay I've got enough I I gotta quit whereas you don't have to have that explicit control in in the the pool model so I'm saying this is rare duck DB actually originally started off being a pool brooch uh and then they decided to switch over to this and one of the things that they highlight is having the ability to uh have a separate control flow control mechanism for these operators made engineering the system actually a lot
36:20 easier snowflake follows this approach as well uh but the like I said the I mention this before the the monb project I mentioned before that like where they they developed a vectorization model those two researchers then went off and built a commercial system called Vector wise that got bought by action and and which is sort of a holding company for for database old databases but
36:45 eventually got killed off but then Marin the guy that developed the vectorization model he then went and became a co-founder snowflake so the guy that invented vectorization model also founded Snowflake and a lot of the ideas that he developed on that earlier Mo ad system is what snowflake is based on today so that's kind of
37:03 cool all right so any questions about processing models or processing directions yes can you explain more detail first under approach to control Yeah question question is what do I mean here titter control of CPU caches and registers and pipelines so going back here
37:23 um we're not going to talk about this right we're not about this semester but like in some systems you can actually just some time compile the code for this because now you're just you're just nesting on to for loops and you can have really tight control of like okay how big should my Batch be okay well I know my CPU has this CPU cach or maybe this this amount of registers so I can decide and what increment do I want to in uh I want to you know iterate over the in the for Loops so I can decide okay I want to keep everything in CPU registers so therefore only look at a single Tuple and then now I can control when I call these things that it's more likely going to sit in CB registers and not you know L1 or
38:04 L2 whereas as soon as you have a next call I mean that's all over because that's a jump in in the CPU instructions okay all right now we're going to talk about access methods um again the access methods are basically the the the leaf nodes of the query plan again this is independent of whether we're doing you know iterator versus vectorization or push versus pull the end of the day we got to get data out of our tables that people have put data in right and there's only really three ways to do it
38:43 you do squential scan which is the Brute Force approach of just reading every single page until you find either what you're looking for or all the tup you can do inex scan and there's a lot of different variations of this based on whether it's a hash table a B+ tree a try or whatever data structure you have
38:57 um and then the third approach you could do uh a multi-index scan you kind of mix and match you have a bunch of indexes instead of just picking one pick a bunch of them and then combine their results right we'll see that in a second
39:14 right and then depending on on the on the sequential scan you know if it's clustered or non-clustered data you can make various optimization choices based on that all right so again this is like the default choice if I have no indexes or no index is going to help my query it's it's the most basic thing you can do and it's you know it's it's probably what you wouldn't Implement first when you build a new data system because it's just Pro it's a way to prove where you got the you know you're storing the data you expect to be in
39:42 there right and so it's a really basic Loop for every single page in my my table go retrieve it from the buffer pool using the page ID right you use the page directory or whatever the mechanism to go get that get get that data uh if it's an LSM you got to basically look at everything uh or just look at what the most you have the way to figure out what are
40:05 the yeah select starf without aware calls in LSM you have to you have to basically look at everything because you don't know whether there's something in a lower SS table that you haven't seen before right that isn't an upper level and you got to make sure that you catch it so again this is example where lsms would be actually worse for this but assuming we're doing uh owner heaps get get every page for every on the page evalate some predic and then and then do
40:28 something and then in our operator as I said before it's basically like an iterator in uh the scan operator it'll be like an iterator in Python where I keep track of my cursor or what's the last page I looked at and the last slot I looked at so that when I call get next or however I'm I'm producing tup as part of the the scan operator I know how to continue along where I left off last
40:51 time so you think okay well this is the most brain dad thing you can do the D system it's basically reading every single page is there any way to speed it up let me take a guess many ideas how to how to make how to make a swiat SK go
41:09 faster what's that paralyze it you said was it vectorization sure PES preload Pages excellent all right three all right perfect we've already discussed a lot of these paralyzation vectorization are new but we already talked about pre-loading prefetching right so think again this is like the worst thing you can do in the da system but we've already discussed a bunch of ways to actually make this go faster right we talked about how to compress the data so that when I go fetch a page I get more tbos than I would if it was uncompressed we talk about pre fetching or scan sharing or buffable bypass if I'm scrunching you know I don't want to pollute my my Breer pool with data I know I'm not going to need right away task paralyzation and multi-threading uh and data paralyzation
41:53 vectorization we'll discuss that next class clustering and sorting we've already talked about that right depending on what my wear Claus is maybe I want to sort of the data first and then look at over the sort of data L materialization we talked about right just pass around the record ID if it's a if it's a column store uh in my query plans and only go back to the get back the data that I eventually need
42:14 right data skipping we'll talk about next uh we're not going to talk about materialized view and result caching in this this class but just think of like it's all caching is obvious select star from data from select star from table where where I equals andd if I see the same query over and over again rather than just running it I just have a cach and says oh yeah you want you know ID equals andd here's the
42:34 result teriz Z is a bit more complicated you can have a more complex query uh that you you you then store as an inate result and queries can then maybe execute get Sub sub portions or subsets out of out of that result cache rather than blindly returning back the the result now of course then this is tricky because how do I keep these things in sync with the actual T the actual table
42:58 we we'll discuss a little bit that uh when we talk about C control code speci leg compilation will we won't talk about this too much this semester but I'll talk about a little bit compilation at the end of this class the way basically saying instead of having giant switch calls and say if my operator is this do that or if my data type is this do that
43:15 I basically want to jit or pre-compile a bunch of stuff ahead of time so that since I know what the data is going to look like because it's the relational T database and I've been told the schema I can say okay I know exactly what this column looks like I know how to run this predicate you're trying to run here's the exact function I pre-compiled that does what you want and it'll run really
43:33 fast all right we won't again these don't want to discuss too much but I want to talk about data skipping so the idea of data skipping is sort of sort of like an index almost like or like a filter basically saying does the thing I want actually
43:48 exist and the basic idea is that it's a way to say I know that there's some subset of a table that I'm trying to scan right now that I don't need for my query because I look at the wear claws I look at the predicates and say uh you know this is what I'm actually looking for and if I have some pre-computed data
44:05 about the about my tables I can make a decision I know there's certain pages or blocks I don't need to read so there's basically two approaches there's lossy versus lossless similar to we talked about lossy compression versus lossless compression right lossy compression or uh data skipping we won't talk about but the idea here is that if I know my query doesn't need to see exact results then out scan every single page I'll just sample the pages and then I could have some kind of statistical confidence to say how accurate is is my my request so in a lot of systems
44:41 they'll have um especially in the cloud system the Ola systems they you know they'll have the standard aggregation functions that we talked about before count min max average but then they'll have approximate versions of those like count approximate I think it's called an oracle so that would be okay well I'm just gonna get a subset of the data and compete your average on that and that's probably good enough for you depending on the needs of the
45:03 application right if you want to say how many people visit my website in a single day you know if it's 999 million versus 998 million if I'm off that much do I really care probably not so there's a lot of different application domains where you you you're okay with approximate results but the data system won't do this explicitly for you sorry implicitly for you you have to tell I really want this thing to be approximate and then some can give you bounds of things right it can get pretty
45:31 complicated the thing we're talk about instead is actually zone maps and basically this this is just pre-computed information that says uh here's what the data looks like at a high level inside a given Pages or a set of pages and then you can decide whether you actually want to go look at it or not and you can have really fine grain zone maps within like a single page or you can have uh more course gr Z M apps for a large number of pages and obviously the the larger is the less selective uh you may actually be you may end up having to look at more data than you actually
46:01 wanted so pretty much every single data system now supports at least in olap side supports some notion of zone maps right so this may be a really simple table with one column with five values right so our zone map would be pre-computed aggregations that we had before main Max average sum count and then say this is this is one page has this data all my other Pages would have similar zone maps and then now when my query comes along select start from table where value equals value greater than 600 so even before I look at the the pages for the data I'll look at the zone map it says okay I'm looking for values where are greater than 600 but I know my max value for this column is 400 so I'll never find a match in this column so therefore I can just skip this reading this entire page and again think on larger scale I'm showing five tles if I had a th tup or billion tupal right then that's a huge win of skipping all that data
46:58 so the open source file format we talked before par and orc they support this out of the box uh and then pretty much all the column store systems will will generate uh something looks like this I'm using the term zone maps that is what Oracle calls them I'm sure it's copyrighted whatever like but that's the sort of the canonical term everyone uses like same way Kleenex as a face tissue like you just say Kleenex me so you say zone map it's the it is the Oracle term but everyone knows what you mean the original paper calls them small uh small materialized aggregations and materialized again means that like I'm pre-computed it I'm storing that pre-computed result so I'm not Computing on the flight and then I can use that from one creat to the
47:37 next all right so that's squential scans like I said there's a bunch of optimizations we can do some of them we've already covered some of them we we'll cover in the future uh in the next class now the other choice again is is going to be an index scan so the idea here is that the we've
47:53 the applications created indexes on our table that we're trying to access and then a query shows up and at run time the data system has to figure out okay what's the best index I I could use for this particular query and there's a bunch of different choices the system can make like does it have the does the index contain the attributes that that are in our query right is is the the predicate going to be very selective if he uses the query or am I still going to have to end up doing complete Leaf node scan right is it a unique index or non-un nonunique index so there's a bunch of different choices the system is going to make to decide what's the best index I want to use to execute an index
48:30 scan that's not this class that's next week when we talk about CR optimization right we're still sort of dealing with high level things at The Logical level although we're talking about physical scans now but how to decide what's the best index for my choice of indexes to use is going to depend on a bunch of different factors and this will we'll sort this out next
48:50 class but let's look at a simple example here suppose we have a single table with 100 tuples and we have two indexes on on table we have one one on the age one on the department right and so in scenario one there's 99 people under the age of 30 but only two people in the Cs Department
49:05 right for this given query the query is trying to find everybody uh that's under the age of 30 that's in CS uh and is you know in school in the US right so now the other choice would be there's 99 people in the stat department but only two two of them on the age of 30 again we have to decide which index we want to use because we have both of them obviously in this one one the index on department is going to be better for us because there's only two people in CS department so if I use that index I'm going to get those two t tuples very very quickly whereas if I use age then I'm basically doing a leaf note scan and then I still got to go look up the tupal to see whether they they're going to match on on the age or not in this case the scenario is the better index is on
49:49 uh so this one two people in the yeah this one better is better index on age because I'm only looking up again I'm I'm just going to find the two people instead of doing the complete scam right so this choice is pretty obvious which we want to use but may the other situations where both of them look pretty
50:09 good and so I actually want to use both of them for my query and this is called a multi-index scan um I think Oracle calls them I think multi-index scans po calls them bit map scans because they generate bit maps and and then Union them or or uh take intersection I'll show next next slide my SQL calls these index merges but all the high Lev they're basically doing the same thing that we're going to use do multi do do
50:35 multiple scans on our indexes get back the record IDs of the matching tuples and then do the either a union or intersection based on whether it's an and clause or an or clause in my Weare Clause to then figure out okay what are the matching record IDs then go go fetch
50:52 them now you see again why we making a big deal about having this uh this sort of generic API for our operator so we can compose them and and in any different ways and not worry about you know one parent has to worry about how the the the shot up is actually producing data because now when I call get next using I'm doing the iterator model with this approach I'm actually going to do the index probes first get the record sets then do the union and then now walk through and find the TB that I want so I did a bunch of work on the first uh the first next
51:23 call and then now any subsequent call will just be reusing those cach results from the from the intersection or or the union I computed right so let's see what it looks like so again so say we have the same query here both of them the indexes look pretty reasonable so we're going to first retrieve the record IDs on age less than 30 using index number one then we're going to get then we're going to now do the look up on the second index for Department equal
51:48 CS take the intersection of of the two results of of the of the the two indexes then go fetch those two bulls to see whether they actually satisfi the last predicate where country equals US my hand waving here probably doesn't help so let's look actually look at an example right so again I first going to do the look up on the age get the record IDs then look up on CS department now the intersection of these two record sets record ID sets are the ones that going to be that matched on this predicate and the other
52:20 predicate right and then now I take take those records that match go fetch them from from the pages right because I know where they exist because I got the record IDs and I convert the record IDs into page number and offset or file number page number offset right we we saw had to do that before now I see how all these things are fitting together I I go get the the records then apply the other predicate and any people that matches that last predicate or this final predicate is then produced as my output for my
52:50 operator right the way postgress does this postgress does this um it's called a bitmap scan because these are actually bit Maps so for every single Tuple in my table the bit will be set to one if if it if it matches here right I think in Oracle they actually do sets and they take the intersection of the
53:12 sets all right so we covered how to do squential scans index scans and and multi-index scans right that's the basic three access methods you have to read data we basically at this point we now know how to run
53:24 selects but now we get inside our database and we got to be able to modify it right so with modification queries yes do we the index on or we it's question is in this example here am I building index on the fly or am I using existing one does not
53:41 matter right again the operator like so you would have so in the case of like SQL Ser they would have a special operator called spooling index scan and it knows to build the index on on any tubal coming from from its child right so you would have the the index scan and below that would be the sequential scan on the on the on the data on the tub
54:01 right but again you can imagine though you could do see get the iterator model you have the index scan the spoiling index generator that the the index Creator and then below that squential scan so youal scan feed tup up to the the the record the the operator then build the index and then that's a blocking call when you invoke that thing then now when you call uh above that basically the index is okay now I have my index now I can start scanning and probing it produce output up above and all the rest of the system or rest of the query plan doesn't know that you created the index on the fly it doesn't matter just you're getting two
54:42 BS all right so we want to talk about how we do inserts ups and deletes um the other dmls or other modification queries you can do are uh there's upsert merge and truncate we don't really to discuss those upserts are just basically I uh check to see whether a Tule exists if it does I update it if not I insert it right it's a sort of shortcut way of doing that truncate is basically deleting all the tubal the way you implement that is just drop the table from the catalog and just read it that's faster than doing a scrun scan and deleting it uh and merge is basically a join producing upates it's like like an
55:18 upsert all right so for insert up delete the idea here is that those operator implementations those operator uh themselves in the system they're responsible for actually modifying the the whatever tables they want to modify and also updating the indexes as well as checking any constraints that may be violated or that are placed upon the table to see whether the change you're about to make is is allowed to
55:40 happen and then the output of these operators will either be the record IDs that got modified or inserted or in some cases if you care about the result of the of the T you modified like if you have a update query you can pass this returning keyword at the end of it and say update the update the query sorry update the tupal or update the table and also return me back the tupal that got modified in their modified form but by default I think you just get the number number of things inserted up inserted updated or
56:10 deleted so for update and deletes the idea is that there' be some lower operator in our in our query plan that's responsible for finding the two pools we want to update or delete and then now they're passing up those record IDs and then those those update delete operators are saying okay now the record ID let me go ahead and make the change that I want
56:29 so again we have these composable query operators think about what your update query looks like update table set value equals true where then some predicate that where some predicate uh that's just a scan either index scan or or cenal scan that's just scanning down below producing tups as part of its output that then feed into the upate operator who then complied the update so you don't need to reimplement uh the access methods to scan data in your update operator CU that that would be redundant and all the optimizations You' have for you know multi-index scan versus other kind of scans you have to reimplement in all the the update operators instead you implement it once in your scan operators
57:09 and then that just feeds tles up to the updates one thing we are going have to do though is also keep track of the tupos we've seen before because now if if we're doing a pool based method like the iterator model where I'm calling get next get next get next I may end up uh in my up operator updating the index
57:28 that then I'm scanning down below so I may like in I may do an update uh that changed the position of some Tuple and now I keep scanning and now the scanning says oh now I found this this another Tuple but it's the one you just you just
57:42 updated we'll see the next slide what what what happens here what this is called for inserts there's two choices one is you have the insert operator itself be responsible for materializing the the tuo that then gets inserted into to the operator this is what busb does uh it's the most sort of simplistic way to do this the second choice and the better choice is just like before where we have Scan operators feeding tubes up into the update delete operator you have some lower operator that's going to be constructing the tupal or materializing
58:13 them and then now when you pass them into the insert operator it just blindly takes whatever you're given it it has to check constraints of course but then it just inserts it into the table so the second choice is better because this allows you to sport select into where you can take the the select output and Route it inside of a table that's just another insert operator into a select query right the select produces the output and then it writes it into a table and and insert operator can keep passing it up so you see the
58:39 result but again this this this interplay of composing things together is really neat all right so let's understand this update problem I mentioned before so let's say we have a table of people and then we have an index on salaries how much money people make right
58:56 and it's the end of the year bonus or something and we want we want to bump up everyone's salary by $100 uh if they make less than ,100 right so again say I'm us doing the iterator model and a pool-based method so I'm going to start executing this thing uh you know for every single Tuple and the child called you know get next this is now going to be an index scan operator and this is going to do a probe
59:20 into my our index looking where the you know salary is less than 1100 so again since this since it's a B+ tree these things are sorted based on the based on that salary so assume I do my initial probe down to the leaf node now I my iterator I'm going to scan AC close the leaf noes and keep giving out tupal uh that satisfy this predicate so the say the first tupal you find is me and I make what do I make $999 a year great right so that then gets passed up as a return result for the mid operator here and then the the
59:54 for that given Tuple I'm going to go ahead and remove it from the index right because we're now changing the salary and then we're going to increase the increase my salary by 100 bucks now I make $199 and then the second part then inserts back into the index with that new value and then I'm done for that iteration in the
1:00:13 loop right but now my index keeps scanning and then lo and behold it's going to find another matching record uh but it's gonna be me again right because I just inserted myself with a new salary I'm scanning along right we're not talk transactions yet but assume I'm just seeing any anything that's in there so now I see Andy at 1099 again and I'm going to go back and uh do the exact same thing I did before and bump my salary up
1:00:39 again right which is obviously incorrect right we want to update every salary only once who has heard of this problem before out of curiosity or is aware of this issue so this is a very famous One in database it's called the Halloween problem uh and this was uh this is discovered by IBM back in the 1970s when they were building uh building system are one of the first relational databases right and so the basic anomaly here is that the in our update operation
1:01:11 if it changes the physical location of the tupal then as we're scanning along we may see that same tupal again because say I'm showing in the context of index but say I'm just scanning through pages as squential scan I may see the Tuple here update it and then gets injected back or inserted back down to a smaller page or sorry a lower page or a later page in that scan and then I keep scanning Then I then I find
1:01:35 it right so it has nothing to do with the Halloween right uh which Halloween is what next week so so the Tim is always right to be able to talk about this and it's and it's actually the holiday in the semester has nothing with Halloween
1:01:50 right the the the researchers IBM discovered this problem on a Friday on Halloween and like oh this is a hard thing how are we going to fix it and they said all right well it's Halloween let's go party and we'll figure it out on Monday right and they just called it the Halloween party and the Wikipedia article uh mentions this and I've talked one people where that I at the time like like they're like oh this is hard let's let's worry about it later let's go drinking
1:02:15 right so the solution and this is what you need to do for project 3 is you just have to keep track of the the the records you've seen before like The Logical records not the physical records because the physical location may change
1:02:27 uh keep track of The Logical Rec for so that you don't try to update the same thing twice CU it should appear as everything when you up update your query under like set semantics or bag semantics you should update everything in in only once apply one operation even though physically you're kind of doing something in a linear fashion yes if we're scanning through the whole index why don't we just like like for everything that we see we update we delete it then we once we're done scanning we insert everything this question is uh uh why don't instead of
1:02:57 from setad of my for Loop removing the index and then inserting it back in want to update things first and then why why insert immediately after removing if like you only want to check everything once so question is why insert everything immed after removing if we only want to update things once uh so in this case here the index is on salary so I have to remove my I have to remove it right we're going to do that now your question is well why insert this right away why not wait till but again always thinking extremes they have a billion people at my company then I have to I have to have intermediate buffer for those one billion tupal to then I have to go later back in update it's just not
1:03:37 scalable yes mod when auge number will be some kind of IND question is if if we have a really large table with the billion tubes would it be thrashing on the index in terms of like page is getting evicted and you have to bring it back in absolutely yes it's unavoidable and also what about transaction you so he says what about transactions when you bort how do you roll that back give me two weeks
1:04:08 yes uh the answer is going to be basically you maintain an undo log so you keep track of all the things you did so that in the case you do abort you got to you got to know how to reverse that so you basically would do you would do the opposite of what you did here give me two weeks on that I love turn transactions are are super awesome uh this is all awesome but B transactions are a really wild way to think about things especially in the contact databases will come to exact
1:04:34 that exact problem later on okay all right so the last thing I want to talk about is how we actually evaluate these predicates which is we've been sort of hand waving about oh yeah a equals 1 a ID equals andd how are we actually doing this so the DM is G going to represent the any predicate that's in awar clause or on clause or any any any projection
1:04:56 uh like you know a ID plus one as part of the output it's going to represent those as as initially as an expression tree and the idea is that the just like a sort of the query plan there's a route and we invoke that and we Traverse down uh in this case we would go through a dep first manner um we Traverse down and start producing uh true falses for our predicate we or whatever the output needs to be for for the expression tree
1:05:22 uh we could represent anything we we we potentially would want to do uh in a datab system so the idea is that you would have these all these different expression types for all various operators the conjunctions and disjunctions the any arithmetic operators uh referencing tupes making calls to function all these be represented nodes in this
1:05:42 tree so now let's sort of a simple example here so now when I want to run a query I'm basically for every single tubo I'm going to evaluate that expression tree over and over again so in this case here so I I I didn't teach you about paired statements but think of like like a like a macro for a for a query I know I'm invoke this query over and over again so instead of calling that you know select star whatever whatever again I can say prepare my query with the name XXX and then now I have this execute operator or execute SQL function or command that says okay I compare I prepared a statement above called XXX now invoke it and then you can pass in now the function 9991 in this example here and that'll get substituted where the dollar sign equals one right it's it's like a simple macro thing
1:06:26 so now say I I'm going to I have a squential scan operator it's scanning table s and now I got to evaluate this this predicate so what's going to happen is I would Define or convert this this predicate as part of the parsing it into the SQL into actually the plan or AB you know plan and I'm would convert the expression into this tree like this so again you just Traverse it in in a depth thst manner so you started here at the equal sign because that's the root and then you Traverse down to the left and this is now a attribute uh look up uh for the given whatever Tu we're valuing
1:06:59 right now uh we want the value of the of the value column a value attribute so for every single T I set up this context information and say Here's the the parameter that was maybe passed in when I invoked the query here's the table schema so I know what the types are that I'm looking at and then here's any uh here's the the current tual that I'm that I'm scanning through that I'm looking at as as I do my examination so in this case here you go look up in the execution contact and say okay the current tubal uh is you know column 1 2 3 First Column is 1 2 3 a th so I look up in my table schema it says I know how to map s. value to what offset of the column that I actually want and then I get my out get my my value like this now again do a death first search go down the other side same thing I reached the leaf note here now it's referencing parameter dollar sign one do the same thing look up my execution context and I went the first parameter so I get now uh
1:07:50 991 jump down to the other side this one's the constant n now I pass it up and now I'm doing super valuation 99 991 + 9al 1,000 that then bubbles up to the equal sign here and then I compare to see whether these values are true if they true then I I produce that as as the
1:08:09 result so I'm doing this for every single tupal as in my table that I I essentially got to Traverse this tree which would be expensive right could be very slow but this is how most systems are actually Implement their expressions for simple things like you know value equals one thing it's not that bad but there's a lot of indirection again because I got to know what the the type of the the expression node is looking at know the type of the values and this can slow things
1:08:37 down right especially in a in a modern CPU I again we're not trying to optimize entirely for CPUs but to be aware of like the CPU wants things to be sequential having to follow down pointers in a tree is is always going to be
1:08:51 bat so a better approach is this we could just evaluate the expression directly right my example here you know select start from table where s. Val equals one so if I have a billion tupal I don't want to have to reverse this tree over and over again to see whether the value I'm looking at equals one what I really want is just almost as if you're writing code a function if you will that just says okay check this expression and just go you know some value that I pass in check just equals
1:09:19 one CU that you can do again you know does something equal something assuming they're two integers that you can do in a in a single instruction in the CPU like x86 will rip through that very very quickly arm everybody will gpus
1:09:33 will So to avoid all of this what I could do is I can maybe generate this code for the query as it shows up uh and then now I basically have a a code representation of the tree then I run that through GCC clang L llvm whatever your favorite compiler is ICC
1:09:52 and then now I have a machine code now I basically have a little function compile code so now when I scan through my table and I look at every single Tuple I don't I don't Traverse that tree I call the function and that's be way faster yes what's the point of having these trees in general this question is what's the point of having these trees in general if I can just compile it well one not every system can compile it
1:10:15 right that's pretty rare uh two you have to represent as a tree anyway in order to then convert it into the the procedural form imperative form right you need it you need a treat representation first because additional optimization you want to do but some systems could could generate this we want talk about this class we talk about the advanced class some will actually Coen the entire query plan including all these predicates right that's actually very very rare very few systems do that
1:10:44 some systems will actually could do this post can do this and we can do a demo all right so uh I have a really simple table um I think it's called fake data right single value column that's that's a big end so the first thing I'm going to do is uh call PG
1:11:10 preor sorry right what PG preor does is basically fetch everything from from dis and make sure that that's in our buer and I set I set our system have enough memory so we we could do this right so my query is going to run uh a really simple thing it's select count star from fake data we I'm just doing some some bunch of arithmetic in the in the in the wear Clause to see whether my T's going to match so po has what they call J time compilation for wear Clauses so let me turn that off first right you set this up with this parameter so now when I run this query we see how long it takes uh by itself without J time
1:11:50 compilation right and tells you the bottom it tooks what the 1.7 seconds um right so it spent uh 0.2 I yeah 0.2 milliseconds doing planning and then 1.7 seconds doing execution again this is the explain output you can see all of the uh you know that it ran in parallel that it it did all these loops and things things like that and then I'm producing the output of the buffers I'm telling it how what percentage of of the or how many pages were in the buffer pool that I got a hit on versus how to go get the disc because I pre pre-warmed
1:12:20 everything uh everything is in is in memory that's good so now let me so it was 1.7 seconds so now let me turn the jet back on and run that same query and again everything should already be in memory so it was an
1:12:42 issue right uh cut cut off keep going down so now the query time went to 1.3 seconds so we shaved 400 milliseconds but you can see in here uh let me let me reduce the size it's kind of jumbled the font
1:13:00 size but you can see that it has the calculation about when it decided to uh to enable the adjust time compilation put it down to 14 maybe that'll help yeah it's a little better okay yeah so again so here you see that the planning time is just before like 0.2 milliseconds but now here's the jit piece and you can see that here's the time it spent to do it right so the total amount of time
1:13:38 was uh to do the jit piece was 200 milliseconds so we got a win our our our query we spent 200 milliseconds to save 400 milliseconds so we the query ran 600 milliseconds faster with jit turned on cuz again I you don't have to reverse that tree for every single tub as I'm looking at it I just compile the function that does you know it does exactly what I wanted to do and that runs much much
1:14:03 faster so Pocus does this uh there's a bit of a cost calculation to decide you know is it worth post is going to try to decide how many tobs do I need to look at what's how long do I expect to take to compile the the the predicate the wear clause and is it worth doing that so in this case here because I had enough tupal I think 50 million tupal it was it was better to compile it spend time compiling then run the query versus just running the query without the
1:14:32 compilation make sense again not every D can do this the alternative and what snowflake does snowflake doesn't do this J time compilation snowflake pre-compiled time and then it sort of stitches those those those functions based on what what's in your predicate again there's only so many data types you can have in in SQL
1:14:56 so what you can do is just say okay I'm going to have a bunch of macros and I'll have comparing to integers less than greater than equals not equals I pregenerate all those functions I compile them then at runtime I now just invoke the function pointer to invoke that that that that function to do whatever the operation I need to
1:15:14 do and because they're running the vectorization model not the iterator model they amortize the overhead of making that function call because they're processing a thousand tupal at a time on a really tight kernel that can rip through a thousand tubes very quickly and using simd which we'll cover at next class uh and because everything is pre-compiled now if it was the iterator model where I was making a function call for every single every single two as I did my predicate evaluation that would be terrible I fully fully admit that it would not be scalable but because again the vectorization model takes a batch of tupol that's why that that technique works so most systems do not do what prus is doing here because there's additional complexity to the Engineers actually implement this data bricks for spark SQL actually used to do something like this they would they would compile the whole query using the scolar compiler and then they got rid of that because it became too difficult to maintain an engineer and it's better off using the the the the snowflake model
1:16:11 where you pre-compile things ahead of time and you Stitch it together I can talk little about that next class but po de this but it's sort of it's very rare as he was asking like you know what if why doesn't do why you bother the expression tree if you can just compile it most systems don't compile
1:16:29 us yes this is just better approach terms of performance compared to the pre say it again with what sorry in terms of performance is this better than preil so question is in terms of performance is this better than pre-compiled uh we actually have a research paper that I wrote with the Germans and the people at CWI came out a few years ago it's a
1:16:49 wash sometimes the the just just time compilation is better sometimes the pre-compiled is better right from engineering perspective the conventional wisdom is that pre-compiling is better if you're doing OTP if you're doing rore you don't need any of this right because there's G to be index lookups to find single tupal you need this if you're doing analytics you need something like this if you're doing olap queries PR is a row store system it's not designed to do
1:17:14 analytics somebody decided they added this a few years ago right again it doesn't always help in some cases again the compilation if the compilation is expensive it'll make a query run first run worse right if I see if I can do this if I put
1:17:30 a put a limit 10 here right same quy before put a limit 10 let see what post does um Still Still decided to compile it which makes sense because it has to know actually why did it compile it it's kind of hard to read this qu plan so it's actually doing a parallel scam the limit see see the very top the limit Clause is at the top right uh I don't have an order by I don't so I don't know why they didn't push down the
1:18:05 limit uh I forget how to turn off parallel queries and post um it's like Max [Music] workers see I can remember this Max and this is like there's different ways to control equals zero or one ah I got it okay so
1:18:33 you see what it does workers maybe do zero so this will do a non hopefully a nonparallel scan now still did workers planned workers launched partial aggreg uh so still compile it but if I do like I just keep it really
1:19:04 simple uh select star from fake data limit one so postp in theory should be smart enough to say I don't need to compile this and and it doesn't right because it says all right go get the first tual it's easy right so again it's trying to figure out what you actually want to do what's the likelihood that it's going to have to read a lot of tbbl in this case here right they had the es say
1:19:36 uh row why I have the actually here's a good example so like this is hard to read me so postgress so this in in postgress query Optimizer this this first thing here this is the a cost of this operator so postgress estimated I'm going to have to read 50,000
1:20:01 tupes right for whatever reason uh but when you actually look at the actual results it said oh I actually only read one tupal so post is off by several orders of magnitude how how many tup it expect to execute here um I suspect because it didn't I didn't run analyze when I inserted this so if I analyze
1:20:19 fake data so analyze is again a post idiom it might be standard it's basically telling it go collect statistics from from this table now and then now in theory nope well now the number is different uh yeah okay so all right so here's what's going on so again postgress is doing iterator model top to bottom so the limit Clause is on the top remember I saying before so the limit Clause it knows has a limit one it expects to only execute one right right and sure enough
1:20:55 it calls get next on the sequential scan once get back to the result and says okay I'm done but the sequential scan operator knows nothing about the limit operator so it just says okay I know I have 50 million tubles I expect to Read 50 million tubles that's what's going on there all right uh I'm over time quick optimizations you do constant folding B recognize that if I'm doing the same thing over and again that's stupid right so if I'm cing upper claws on a constant
1:21:22 let me just run it once use the constant over and over again that makes things run faster another common Sub Sub sub subexpression elimination if I see the same sub expression being evoked over and over again again I can just ex compute it once and reuse it right all right so finish up the the same logical query plan the same query if you will can be executed a bunch of different ways it be tradeoffs for uh for various systems what what the data looks like what the hardware looks like uh and so
1:21:52 you have to design the system with some expectation of what you think is actually going to come down the pipeline most systems most system most especially LP world you're going to try to use as much in skins as possible and try to avoid squential scans but we saw a bunch of Tricks we could do to avoid having squential scan everything if we could the expression trees are flexible for us because they we can represent anything but they're going to be slow and jit compilation can sometimes speed things up if if if we're on the right situation
1:22:16 all right so next class we continue on query execution but now how to talk about how to do parallel query execution so basically how to take our query plan and now instead of scanning a single you know one thread scan a single table at a time one table at a time scanning parallel need something refreshing when I finish manifesting to cold a whole B like Smith and Wesson one court and my THS hip hop related WR a rhyme in my pants intoxicated lyrics are quicker with a simple Mo lier since on City Slicker play waves are picker rhes I create rotate out of you quick to duplicate feel a breeze at a skate mik at Fahrenheit when I holding will I'm in flight then we ignite but starts to boil
1:22:58 I heat up the party for you let my girl R me my mic down with oil W still turns with third de Burns for one man I heat up your brain give it a Sunan so just cool let the temperature rise the cool it all with odds
1:23:15 [Music]