CMU Database Group · 1:21:18 · https://www.youtube.com/watch?v=X8EHO8VLeG0
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 licks and M Clips the Chrome will make the average imitator do back flips you like a [Music]
0:27 pistol all right so today now we're going to talk about uh query optimization query planning right how do we take a SQL query and generate a plan we actually want to run um before we get into that the logistical things in the class are uh again project two was due last night project three came out yesterday as well and then given that we were late in releasing it we bumped it up another week uh so you'll have now three weeks completed instead of two so we do on November 17th we'll announce the recitation uh next week homework for four will still be due uh this Sunday
1:00 coming up at at midnight yes question we're try to release project 4 the question is if project 4 lease dat be D bumped we're going to try to release it sooner and then given that we have potentially less time now work on Project 4 we'll pair it down a bit of
1:17 it okay any other questions and as far as I know they haven't announced the uh final exam dates and times yet so when I missed that okay all right uh the okay whatever he said Friday 13th and then we'll forget you know if it's in the morning we'll get coffee and donuts and cigarettes forever you want okay um for uh for again for additional database talks we have somebody today coming talk about a database they built using data Fusion for specifically designed for bioinformatics and then Sonata is giving a talk the following week their streaming system and then influx DB is the only database company we've had talk three times here at CMU
2:00 because every time they come back they're like yeah we made a mistake here's a new system we're building so they came the first time we told them that they were doing wrong and then they went ahead with it anyway and then came back the second time said oh that was a mistake uh we had to redo it and then Paul's going of give give a talk again with us in in a few more weeks and saying again now they're based on data Fusion but before they were using map and I tot was a bad idea uh and they
2:20 they were they didn't believe me and then I was right okay all right so again last class we were talking about how to take a query plan uh that some piece of the system generated which we haven't really talked about which today's about and run it in parallel I mean prior to that also too when we talk for separate query execution was how do we architect the system such that we can move data between the the different operators um
2:48 and you know removing the whole tupal part of part of the tupal uh batches and so forth and the thing we were talking about is is at that level was we were talking about these physical operators in the query plan right it was no longer I'm doing a join in an abstract way I was saying I was doing a hash join or an EST Loop join or C join or I was doing my I'm doing a looking up table or data from a table on the index or a or the actual squential SC on the table itself so today's class is really trying to understand okay great we know how to execute the queries now but how do we get those query plans
3:21 how do we go from a SQL query and then generate the physical plan that we can then execute on our on our system right using the processing model that the that we talked about before so that that's what really today is about so to set things up let's do a really simple example here we have a join on an employees table and a department table
3:40 uh based on the department ID and we want to find up all find all name all the employees that work in the toy department so this is the SQL here we're given and then we haven't really talked about cataloges uh a little bit we have but not in detail but think of this now there's some internal database of metadata about what's in our database
3:59 here's the table I have here's the columns they have here's the types that they have here's the indexes I have on what tables and is it clustered or unclustered and some as we saw before some basic information about I have you know so many records so many tupal in my tables and they're broken across uh so different pages right so if you take this SQL query and almost do a little translation of it into relational algebra uh you will sort of end up with a a query plan looks like this where at the at the leaf at the leaf nodes we have our scan hands on the employees and Department table then we're feeding that up into a a cartisian product um and then the output of that gets filtered based on the matches of the joins then there's additional filtering we're doing on the uh on the department name and then we do a projection at the end to produce the the the employee name as the
4:47 output so if you want to start calculating the cost of this because that's the thing we really care about now when we start picking deciding what query plans you want to use for given SQL query uh we need again we're use some some approximations uh uh or estimates based on what we have in our catalog to determine whether one plan is going to be better than another so just quick back of calculations what we can do here is say okay well I I know I got to scan the employee table and the department table um and so there be 500 500 reads for page reads for this
5:20 um million page reads for that and we're going to take all the output and just write it out to to a temp file right so then now uh the the the next operator is going to take that temp file as this input read it all back into memory uh do the filtering and let's say again that's it's a forign key join which just back of back of the envelope calculation we're going to say
5:45 uh that a certain number of T is going to match so we're going to only have to write out 2,000 uh 2,000 records so then now we write that out into a temp file T2 that that's gets read in by the the second filter
6:00 uh and then now again we're doing some filtering say it's it's we'll have 50 employees per Department right assuming uniform distribution which cause problems for us later on uh and then we write that out to another temp file which you then just read it back in in the get the employee name and do the projection right so for this gross approximation we're doing about two million ios's uh which is not great
6:22 right and so the question is okay how can we start in aqu quer Optimizer start reducing this IO cost because that's going to be the dominant thing for us and again whether it's coming from disc or coming with the network at this point it doesn't actually matter uh you know what can we start doing to start optimizing this further well the most obvious thing is that we have a cartisian product which is almost always going to be the worst thing we actually want unless someone explicitly ask for a cross join in our query we almost we never want to be be doing a cesan product or cross join so we can just replace that with a uh a block based or Nest page based nested Loop join and then now you know the amount dat we have to write out after you do the join is is significantly
7:03 less we then feed this now uh into our projection or sorry our filter operator who's now reading less data it's going to write out the same amount before and then the uh the projection at the top is going to do the same amount of work so now we got it down to 54,000
7:17 iOS again just by just replacing that cartisian product with a page based or block based nested Loop join right we've done we've read less data at at the leaf nodes can we optimize this first further of course we spent a whole lecture talking about crappy uh how crappy nested Loop joints were so what if we did something better like a sort join right just Again by just replacing this join
7:44 algorithm the decision we're making in our physical plan like instead of using n Loop join replace the physical operator with a sort merge join now that reduces the cost of the amount of iOS we're doing by quite a lot now we're down to doing 7,000 iOS for this one
8:01 query what's another thing we could optimize we talked about query processing models right we talked about the iterator model we talked about the materialization model we talked about the vectorization model this is the materialization model because I'm taking all the output of this physical operator writing it out to a file and then reading that file back in at the at the the the next operator now ideally if you can keep everything in memory sure that'd be great but let assum assuming that we can't in this example here so the materialization model is going to give us 7,000 ios's but if I'm if I'm smart about this and realize well if I use that then I'm not doing any
8:44 pipelining uh if I switch to a vectorization model I get rid of the the rights the reason wrs down below the leaf notes Here I still got to read everything in but I don't have to read it back in in the other
8:55 operators right so so just by switching to pipelining I'm getting down to 3,000 iOS now in a in in most database systems nearly all dat systems they're not actually going to be able to choose between M materialization and and uh vectorization model they usually just Implement
9:12 one but if you then if you are care about how you organize and uh what operator executes in what order then you can avoid having to spell a disc unnecessarily and you can get get more better pipelining right so this is like this is like an extreme case of like no pipelining all pipeline but toit more Nuance when you actually do uh further refinement of the query
9:34 plan all right so now we're down to 3,000 ios's can we do better what's another thing we said we we we can do when we start figuring out how to make the joints better swap the inner with the outer right and then obviously also here I have this filter up here of filtering out the Departments based on the name the department name well I clearly want to do that before I do the join right
10:00 because why do join a bunch of tupal uh on departments and and then just going to filter out later on so I want to consider swapping the employee with the department and I want to also consider moving down the the the filter the the predicate below the joint so if I do that now switch flop this move this down slide this over here
10:21 right now the uh on the Department case I can start using index next index lookup because I have an IND index on the the department name where am I up up uh here right I can do a look up on the department name that's going to be fast now I'm just doing a lookup for give me the department where the department name is toy that's a single look up to get that right and assuming I still have to write out the material materializing the output and then now when I'm doing my join I'm doing much much less work on the joint because I'm not joining tuples that I don't care about anymore and in this case here I just do it Ina Loop join because now I have a department
11:00 ID and I have another index on Department ID on on the employee table so now it's just a single probe to go get all the uh all the employees in that department assuming that there's 20 of them and then now I feed that up and I'm still doing that final uh projection on the the tuples at the end so now I got it down to 37 ios's we went from 2 million doing something really stupid to
11:26 37 so that's what today is really about how can we get it down how can we take a query plan that if we do the naive thing again almost a literal translation of the SQL query into relation algebra now there's not always going to be relation algebra constructs or everything in SQL but high level I think you understand what I mean but how do we go from something that's terrible to something that's good enough and dats are amazing like when you sit at the terminal and like duct B and SQL light and post or whatever when you write your SQL query
11:54 and hit enter it's going to do all the stuff for you and then then run the query it's very impressive all what these systems can do all right so today we're going to talk about again the High background about cre optimization is going to be about then we'll talk about the B main two ways to do coronation one will be rule-based or heris sixs similar to what I showed here before where like I actually don't need to consider whether this is a good know doing a switch is going to be a good idea I mean switching the switching The Joint algorithm that that requires uh more thought but like predicate push Downs almost always are going to want to do it and so the bu of rule based optimization can do and this is what most systems build when they buil build quer Optimizer the first time
12:33 they're going to build something that looks like this then we'll talk more sophisticated more more complex way to do this using cost based optimization we'll finish up then talking about what how to actually do these cost estimates all right so I have three warnings for you today's class first of all buckle up this is hard okay the joke in databases is that if you try to make it in quer optimization and you fail out and you can't do it and your backup plan could be a rocket scientist because doing rization in a SQL database is much harder than doing rocket science whether that's true or not you know it's debatable right I say also tuned the second warning is this is the part of the DAT I know the least about right uh I you know today we're rely scratch the surface I could talk about some what the
13:14 what other systems do but like the the lowlevel rules and all these uh AA of things you can do to optimize uh queries it's you know something that I'm not really I'm not I would not say I'm an expert at all you know who's the expert in this the sorry I the German who wrote that umra system he wrote his own quer from scratch right so not only he has the best query he has one of the best engines it's insane sorry
13:37 um and then last one would be the good news is that it's not really a warning that if you're really good at this I'm not saying this one lecture will you'll be an expert in this uh we'll talk about $7.99 next uh at the end of the class if you're really good at this you can get paid a lot of money because the databas companies when the email me and say hey do you have students to hire they always say hey do you have any students working on crit optimization we really want somebody who works on crit optimizers
14:00 right so this is always going to be demand the rest of your life because it's just so hard and every datab system has to struggle is going to struggle with this and no a and llms aren't going to magically make this problem go away
14:10 okay all right so at a high level what's going on here so your application is going to send us a SQL query over the network or or through a local connection and it's going to hit our databas system the first thing we do is hit a parser
14:23 and the parsel is going to take that SQL query and convert it into an abstract syntax tree now there's libraries now like SQL parser in Python there's a sorry SQL Pars in Rust uh there's lib PG lib PG query in in C++ or
14:40 C all right uh like there there's libraries that can do this for you most systems now are going to try to speak the postest dialect so there there's a modular version of the pogus uh parts that you can get so that's going to spit out an abstract syntax tree you then pass into the datab system binder and the binder's job is basically take string tokens of of database objects like a table name and then map that to some object ID or internal ID in in the
15:06 catalog right in post there's a PG class table that sort of that where you store all this right but again it's just making sure that if you're reference a table that doesn't exist the binder will will check it the parser is basically checking whether you're sending uh malform SQL
15:22 queries so then the binder is not going to produce a a logical plan that's basically to say here's the joins I you know I want to do here's the here's the the tables I want to reference here's the projections and filters I want to do again but the logical plan doesn't specify how to do it it just says what you want to do you then pass that into the optimizer and depending whether or not it's doing uh cost based op optimization there'll be a cost model component along with the catalog well usually sort of the statistics in the catalog anyway but there's be some component that's going to say okay for different physical plans I could have for the logical plan I was given here's the ones that I expect to take the least amount of time to execute or have the lowest
16:04 cost and then this will crunch for a while and then at some point it's going to spit out a a physical plan that you can then actually finally execute so when you call explain in like postgress or duct DB or SLE light that thing coming out you see the tree structure that's the physical
16:21 plan all right so just reiterate the logical plan is going to tell us what the uh what we want to do at a high level and then the physical plan is going to say for for given a logical
16:32 given the logical steps I want in my query plan here's how to actually physically execute it like if you want access this table use this index or do binary search on the the sorted table or if you can do a join do a sort Mage join instead of a hash join and you even get more fine gra things like do a hash join but but allocate the hash table to be this size when you run or use this hash function and so
16:51 forth so they're all always be a one one mapping between a logical plan operator to a physical plan operator right like you could have a logical join and a logical order by and then that could be collapsed down into a single uh sort merge join because that that gives you the order by property you want and does the
17:10 join right and in some cases too you take you get a logical plan and break that up into multiple physical plans right so there isn't always going to be a one mapping between these the these different plans back and forth and typically you know when we talk about the actual implementation what'll happen is you'll you'll once you have the logic plan you convert it to a physical plan you never convert it back to the logical
17:33 plan right like it because it doesn't really kind of make sense to say I know the hash joint is the best thing I want to do why would I go back and lose all the information I've collected doing that optimization to go back to a logical joint operator sort of the transformation occurs in One
17:48 Direction all right so what are we actually doing at high level here so query optimization is a really hard problem uh it's been proven to be MP complete or sorry MP hard if you account for the the different join ORD you can have just think of like different ways different permutations that can have for joins that right that by itself is is going to be empty hard
18:07 so then now the idea is that we want to find a b bunch of different logical plan candidates and then for each of these candidates we're going to then try to estimate the cost of them if we're doing cost based optimization and then we at the end we either run out of time or we exhaust our search and we say okay here's the best plan I could have right now physical plan I'm going to go ahead and execute this so the reason why this is really hard just think of like here's the the giant entire search space the solution space for all possible uh uh query plans I could have for any any complex query and then there's no way we're going to be able to explore everything so we need to be intelligent to decide how do we jump to someplace inside this uh total solution space and muck around or look around and try to find a reasonably good plan uh in a short amount of time because practically it's just not possible to do an exhausted search for simple queries sure
18:57 like select star from table where ID equals one and you have you have an index on ID you can find the optimal plan right that that's easy but when you start doing joins and again think of like six joins seven joins seven way joins the craziest on i' ever heard is maybe up to a thousand joins right because they're all machine generated uh uh queries it's not you it's coming from a dashboard not like a human typing these things and in that world you know
19:22 it all it all comes all comes falling apart uh nobody does those things well except for the Germans okay uh because they have a yeah they have another technique we'll cover later okay right so this is the big picture what we're trying to do here and as I said the two general approaches we're going to do are
19:38 uh apply rules and heris sixs that can rewrite the query to remove things that we know is probably going to be a bad idea to do right the predicate push down is the most obvious one like I want to do I want to filter things before I do my my
19:53 joins not always the true right you could have something like the predicate does in a very expensive calcul or makes a call to like open AI which cost money now and maybe I want to do that after I do the join because I don't want to pay money you know do outo outbound requests um but in practice you almost always want to push that down in some cases we we almost always have to maybe look at the catalog to understand what's going on but uh the key thing to understand about these heris and rules is that they don't require us to actually look at the data
20:23 because at this point when we're optimizing the the the query we can't look at the data because the query hasn't even started running yet my SEO does something I don't know if it's a good idea or bad idea but they're the only ones does this I need to understand a bit further in some cases they'll actually run part of the query during the during the cizer they'll go run the part of the query get back some information and then say okay yeah let me let me based on that let me go decide how I want to do certain things some systens will do this for sampling to collect data we'll cover that later right but in general you for these rules and ristics you don't look at any any
20:55 data and then the alternative again is going to be the cost base search these are do not meic exclusive most systems will do this one followed by this one postc does this one a couple times does this one and then goes back to this one again right because it's kind of a hack but um we we'll cover these things later all right so let's first talk about how to do uh the rule one so the rule one is really about doing logical plane optimization and then the idea here is that we're going to have these rules basically patterns that we want to match on our query plan
21:26 and if we see this a pattern getting satisfied we know it has certain inefficiency that we want to remove and then we apply a transformation rule to then do the rewriting to change things and the basic idea here here is that we're throwing away things we know are stupid uh and kind of pushes the the query plan towards the direction where when we have to do a cost based search which is more exhaustive that we're kind of in the right location uh at least at a good starting
21:53 point so in this world though we can't do any comparisons to the side if I do this transformation is it better for me or not because again there isn't going to be a cost model that says this is one better better than another right it's again it's sort of ingrained or implicit in the implementation of the rule as database people building it we know again predicate pushdown is going to be a good idea therefore always do
22:16 it right so again in this world we can't guarantee we'll be able to find the optimal plan but in practice this gets us in the right direction which again will help a lot so these are the examples that we saw before the predicate push down right and then now maybe instead of operating directly on the on the uh on the query plan tree itself I could operate directly on relational algebra because that maybe is more Compact and easier to do easier for the the system to reason about so in this case here again I have the the the filter on Department name above above the join I just want to move it down to be below the join and so I can just re you know match that pattern either on the the relation algebra expression or on the tree itself and then go ahead and do the rewrite that
23:00 way and that's fast right and so typically what happens is when when these systems get implemented they'll be uh well in some cases postest it's much if then else statements which is not great and other systems you could Define the the rules uh maybe using a DSL and then you set a priority say I always want to check for predicate push down first Then followed by this one follow this one and post is a bit tricky because you have to do certain rewrite rules in exact order otherwise the tree ends up in a invalid State um but in
23:34 theory you should be these things should be composable all right the other rule we saw before was doing the the replacing the cartisian product again if I just see a cartisian product with a the filter right above it that actually has the or claws to my join right that's a no-brainer I want to rewrite that into a to an anner join right and this you remove that filter entirely because the filter goes inside of now the joint operator here
23:59 right again I don't really care what's above or below uh me I can sort of I to pattern match on this part right here and then I just keep everything else the same because I know that again I want to get rid of the cartisian product it's always going to be a good
24:13 idea and then the last one we saw before again was projection push down if I know that I have a a projection above a join that's going to throw away most of the data that that I would actually need or not throw away most of the data that's coming out of the tupal
24:29 then I may want to duplicate that projection operator to be below the join and then now I can do a calculation say okay what's the minimum number of attributes I need for this table feeding up to the join and filter that out uh project that out so that I'm only passing up the the small number records I need now here's where you imagine a cost model could actually help right because if my if my my table has three columns then spending the time to actually do this projection and copying data from you know from the the scan into the the join
25:02 might be actually wasteful but if my table has I don't know 10,000 columns then yeah this projection push down would be a huge win so oftentimes in these rules you'll see hardcoded values you'll see them in the cost models too where like someone says okay yeah 10 if it's more than 10 yeah do do the projection push down if not don't do
25:23 it yes so is projection helpful for this question is projection push down helpful for RO St deat yes so my example again if I have 10,000 columns and I can calculate my Optimizer that this query only needs two of them then I can throw away the other you know 9,000 of
25:44 them right so not just col stores because again like think of like in my example of the materialization model I was I was copying from one oper to the next right I'm I'm wasting space copying those extra there's extra columns that I'm not going to need right even it's pipelining I can I can keep more things in memory if I'm not polluting with with data that I don't need the end of the day the goal of of the cizer really is trying to throw away as much useless things as quickly as
26:13 possible at at a reasonable computational cost all right so again like the pretty much every single data system is going to do some version of of these kind of rules because again they're fast they're easy to implement reasonably and then they're I said they're almost always going to be the right thing to
26:34 do all right so now the next thing we to discuss is to do cost base search and this is the part where things get really tricky right and so the idea here again is we have this logical plan that we're converting to physical plans but there's a bunch of different candidates of physical plans we could have right I show the example like I could do a I have a join I do s merge join n Loop join index n Loop join and so I need a way to say okay of my choices to do this this one joint operator which one is is the best one so the question is how do you actually start enumerating the different choices that I have and reason about them and decide you know how to guide myself towards an optical solution
27:14 I would say also to this cost model being for this cost that referring to this estimate this is going to be an internal cost that is specific to a database system's implementation and is not sort of uh comparable across other systems meaning like process is going to spit out a a query cost estimate for its queries and if I take that same query run my SQL it's going to put out a number two and says this is the cost those numbers don't mean anything across systems it's only do relative comparisons within the system itself
27:41 because certainly also too if the data changes the hardware changes or other parameters and tuning of the system changes those costs actually might change within uh the system itself all right so in our example here we're going to start with a sort of the most basic uh cost based optimizer uh to bottom up cost optimization this is actually the first cost uh cost based Optimizer that was built by IBM in the in the 1970s right so basically IBM invented how to do cost based cord optimization back in the day because one
28:12 they didn't exist and uh two they realized okay with something declara of like SQL you need a way to to compile it and generate a an optimal query plan similar to how your you know the C compiler compiles C code into assembly or machine code
28:29 so what they're basically going to do is enumerate a bunch of different plans for the query and estimate their cost and they're going to have uh separate sort of paths or or passes to handle the case when you have a single table in your query multiple uh tables in the query because you're joining them and then the hardest one El do is potentially also subqueries or nested
28:48 queries so again the optimizer can be able to run for uh enumerating all these different plans trying them out until either it realizes I've seen all possible physical plans and therefore I know which one is the best one like in the optimal case right you can do that for single single table queries it must never can do it for uh
29:08 above three things get things get tricky um or there's there's a timeout like in postgress and myo and all these other systems you can specify how how long you want the query Optimizer to actually run right again the trade-off is going to be
29:20 say my query is going to run for 10 milliseconds do I really want my query Optimizer to run for 100 milliseconds or maybe I just let it run for 10 milliseconds and then I'll find a query that runs in 20 milliseconds and I'm still ahead versus doing you know still running faster than is letting the the um quer try maybe try to find the true optimal
29:39 plan right again the key thing we can't do exhaust of search here because everything's going to be because of the problem's going be end be hard all right so as I said the if it's a single table this is easy because it's it comes down to me what's the first what's the best access method for my query right do do I do a squential scam which is always the fallback method for for a table uh is there is my is my data clustered on index therefore I can do binary search maybe choose that or then I try to pick the index that is going to be the most selective for my query again if it's a primary key look up on and you have a prim you obv have the primary key index that's easy like select star from table where ID equals Andy and I have an index on ID that's easy where things get tricky now if you have like doing a lookup with the wear claws on A and B
30:27 but I an index on a and then a separate index on B how do you handle that we saw how to do multi-index uh scans before because you combine together to the results take an intersection right so there's all those things this is where we have to figure those things out we won't talk about predicate evaluation ordering but that also matters a lot as well because I want to be able to throw away as much data as I can quickly as possible so therefore I want to evaluate the predicate that's going to be the most selective right
30:55 away right if if it's uh find me all the the email addresses that end with do. cmu.edu versus all the names where the last name equals Pavo I think there I'm only here at CMU so like that index on on the index of name to find people named Pavo that's going to be way faster than looking at everyone has you know cmu.edu email address and then the the query app members can then figure out how to reorder the the those predicates based on those cost
31:24 estimates yes but how would it know that there's less C CM his question is how would you know that there's more Pablo at CMU sorry there's more C how would you know that the Pablo email uh Pablo name is more selective than the email we'll see this in a second that we'll have statistics in the catalog basically histograms to keep track of what the data actually looks like right you it's never going to be perfect it's often really really wrong uh but it's going be better than nothing but you'll have some information
31:53 also too you could also look in the catalog and say like um well say instead of looking up last name equals Pablo where where Andrew ID equals a paavo in that case you know Andrew ID is unique right they had some had paavo they won't give give it to me from 20 years ago and I think the guy's dead too and they won't give it to me anyway like that's a unique key and you look in the C and say I know I'm doing a lookup on a unique key and I have an index on that unique key because I have to have it to be unique that's going be way faster do that lookup first so there a combination of the catalog and some basic statistics we're
32:25 collecting okay so now okay simple simple query or you know single relation queries this is easy the tricky one's going to be M when you have multiple tables I'm going to show two approaches the first one is going to be with the system R1 that sort of mentioned the classic approach the bottoms up uh dynamic programming style where we start with nothing in our query plan right we start with like this here's all the tables that I I know I need to join them
32:49 and then you build it up iteratively uh start doing the joins and try to figure out what's going to be the best join ordering and the best algorithm as you go up and then you just choose the one that has the best call the the best path going down getting back to the starting point and then the alternative will be this top down approach or transformation
33:07 where it's like a branch and balance search where you start with at the very top like this is what I want my query to produce as an output and then you work down start adding in the The Operators to get you back to where where you want it right so idea is you start with nothing uh the first question is you start with nothing and build it up the last one is you start with the the answer you want and then prute it down to generate the plan you
33:31 want so I'll go through each of them so as I said this is the first the the first C Optimizer built by at IBM is this bottomup approach um and what they would do is they would first apply a bunch of static rules we saw at the beginning to to throw away things you know are going to be stupid and then they're going to do Dynamic ordering uh dynamic programming to figure out the best joint order for the the tables
33:52 basically doing divide and conquer approach right and they said most database systems that are open source are going to be using some variation of this uh I don't know what click house does the German umra system does a
34:06 a cocaine fueled version of this uh with hypergraphs uh it's very again we'll cover this in the class next semester but this is the basic building block for that help most systems do create optimization so way system R would work is that they would first break the query up into blocks uh sort of think of like a join and two tables that was going be considered a block block and then they would figure out the uh The Logical operators of the block they want to figure out how to do the the the pick the best joint algorithm and the joint ordering within that block and you sort of construct together now the query from all these blocks that that you're you're
34:43 you're building up but one of the key design decisions they made in their implementation is that they would only consider what are called Left deep trees so a left deep tree would be like I'm joining A and B and then the output of that I join C and the output of that join it can join with d contrast this with a bushy plan is something like this where you would join A and
35:04 B I join C that produces some output and then I join the two joins together let me take I guess why uh why did IBM decided to throw throw away the bushy plans hard to construct a lot of pieces he says hard to construct a lot of pieces yeah so one that's one answer right that you if you just throw away any of these any bushy plans that look like this or anything that's not a deep tree that cuts down the search space quite a bit right all right so why why would they only want to consider these then right because I I could just say I'm only taking bushy plans throw away all the left deep and right deep joins
35:38 so why I only do right deeps pipelining right I join a and b and then the output of that as those tupal come out right I can then just feed that up now join join with C so what you could do is say you're you flip the order this say now you're going to build these are all hash joints you build all the hash tables in b c and d do a first pass on those you build the hash table on those guys all right now you come back and take a and you can write a at the pipeline you never have to spill at the dis if you say okay Do my a check to see where it's in the hash table for B if yes check to see where this hasht C if yes check D and then so prod your output
36:19 right so if if b c and d are really small you do one pass on over them build your hash table then now a is the really big table and I'm just scanning through that once doing my probes in all these hash tables and see whether I have a match I can op on this even further again as we talked about before like as I'm building the the hash tabl on BC and D I could build the bloom filters on them as well and then now as I ride this up it's even faster because you know if if the 2. a doesn't pass the balloon filter I never have to go you know you know I don't even even probe the hash table so I can keep those balloon filters in memory and only go get go to dis get the get the hash tables if necessary if I'm if I'm really constrained on memory
36:57 right so they do this for pipelining and because again it's 1970s the computers are really slow uh and memory is really limited it cuts down the SE search space a lot yes whener when operators are communicating through M they go the question is when uh when operators are communicating through memory do they go through the buffer pool T
37:20 typically doesn't they don't have to but if you think you're going have to spill a disc then you want to basically have temp buffers you right into that could spill a dis so in post yes they they they they will be backed by blocks that can spill a dis in other systems they could say all right well I want to run fast as possible I if I run out of memory I'll just reject the query right right and then you come back say give me more more memory you could do
37:46 that right so if you have to spell a disc it has to be back by the buffer pool but as we talked about before it's it's a it's like this temp space a scratch space that's assigned to your as a query that nobody else can read and write to and and it could get evicted sure but it's not like someone else going to take the P the page lock on it way you're
38:08 running all right so let's look at more more uh more complex example here so now we're doing a three-way join on a sort of Spotify example we're going to find uh all the artists that appeared on My remix from a few years ago and we sort it by artist ID so we're doing a joint between the artist table the appears table and the albums table this example we show the first day of class so what system would do is the first thing you got is say okay I need I know I need to access the artist table the appearance table and the Alum T album table so let me just choose what's the best access
38:37 path uh for each of these and again you can just do this in the catalog using rules and say all right I know I got to do a cenal scan and artist and appears because I don't have an index that can satisfy any of the predicates in my my wear Clause my joint Clause but in the case of album I can I'm doing a look up on name and I have an index on that so I I can use
38:55 that then now you're going to write all the possible joins that you could do for this for these three tables right because this is Powerpoint I can't show all of them right but it's not only you know am I doing inner joins but also for all the cartisian products as
39:12 well and then now you going to detm the Joint ordering one of the lowest cost again the rule you apply is you need to throw away anything with the cartisian product because you don't you don't want to consider that uh but now it's really now been trying to figure out for the ones that are doing joins what's what's which of these is the best ordering and then also which which joint algorithm do I want to use as I'm scanning
39:33 along all right so again the the system R Optimizer is a is a Bottoms Up approach so we're going to start at the bottom here that we just have this logical plan that says I want to have I have artists I have album I have it appears join them I'm not saying what order yet I'm not saying how I'm to do it but that you start that that's the starting point and then the thing at the top is here's the logical output that I want I want I want to produce the query result when I join these three
39:59 tables so in the first phase here you then say all right I can have uh different orderings of the do the joins so I could join with artist and appears first or album appears appears an album and dot dot dot because it's PowerPoint this goes on uh quite a while and then now the path from that starting location at the bottom to the next stage the next logical operator along this path will specify here's the physical operator I want to use to compute this I pass join versus assort Mage join right and now I'm just annotating again with just the predicate that that I I'm using to do that join so now for each of these paths
40:38 I can then go to my call MoDOT and say okay to join uh artists and appears using a hash joint how much is this going to cost me how much dis am I going to read how much CPU could I potentially use or for the sort mer joint to do that same joint if arti appears how much CPU how much disc whatever else I want to use my cost model I then calculate the cost for for that path
40:58 and then now for each of the uh logical operators at the next level I just pick whatever path that is the has the lowest cost and throw away everything else right because under Dynamic PR the principal OBS of mality if something had the lowest lower cost going up here uh then in the global optimal uh Global optimal plan it has to be part of uh it has to be the lowest cost between this decision right here at that
41:24 level so at this point here I don't know which of these three choices or as it extends out all the different choices of the physical path going to the next level is that has the lowest cost but this stage here I know from here to here this one has the lowest
41:37 cost and again I'm only s SB join versus hash join nested Loop join all the different variations that that we talked about before could would be part of this as well so now I want to do the same thing so now I say okay now I have Artis and appears and I'm joining with album and then likewise for all these other guys here so now I say well what's the path the different joint paths I could take up to get me to my final final
41:59 result per or permute all the possible enumerate all the possible uh joint algorithms I could have for each of these compute the one with the lowest cost throw away the rest and then now I want to say okay now that since I'm at the top I have multiple paths to get me down to the bottom which one is going to have the lowest cost and that's the one I'm going to
42:23 choose make sense this query is actually this plan is actually not even correct though right what's wrong going back here I have an order by Clause right but in my when I choose my path going back here there's no notion of ordering here
42:49 right so one of the limitations of IBM's first uh implementation of a c Optimizer is that they had no no the physical properties of of the data sorting is the most obvious one um you can imagine compression and other things right so the hack they would do to make this all work and modern systems can fix this um the hack they would do is that they would keep track of the plans that had with and without the the the Sorting property or whatever the physical property that I cared about and then they would check to see whether for the plan that didn't have that guarantee that physical property if you tack on whatever operator you need needed to make it conform to the property you want like added added order by Clause add a sort clause or operator above the join to get it to to the the form that I need
43:37 if that cost was less than the uh the one where that the the query plan satisfi that property then I would choose that one by just adding at at that sort thing so they using the cost model to get it to to determine whether the physical property was what actually I needed to produce the actual correct plan that I wanted
43:59 Mak sense yes so is the cost of a for Oney will be different for different or all be the same this question is is the cost for is the cost of a has joint different per query yeah yes absolutely because so for order
44:17 bu has lower cost question is for a a uh question is if if we we're join equ with an order by clause wouldn't the the sort joint always be better no hash joints are hash joints are proven to be uh algorithmically
44:36 better than more efficient than sort join right so maybe the case depending on what the the data looks like uh doing the hash join making the data unsorted then doing the sort afterwards that actually would be the cheap the better way to do it right because say the hash only produces two
44:54 tupal then then that would be you know that that's be just faster because then the sort cost is so small maybe another way to say is maybe what you're asking is is the hash joint cost always going to be the same regardless of what query I'm looking at no it depends on the data coming in depends on the join Clause how selective that is right depends on the hardware depends on how much memory you have depends on all these different factors that are very hard to to
45:21 determine and estimate I see what coration is it's very hard yes there you go the light bulb just went off fantastic yes this is super hard um I mean you so you can play some games of like recognizing if if the data hasn't changed like I've never seen update insert updated query and I see the exact same query over and over again could you reuse the if you know could you reuse these estimations
45:48 yes but often times that isn't the case yes if we only keeping track of the best parts isn't that more like a greedy approach question are you only keep track of the best paths isn't this yeah so this is not going to be the global Optimum for the choices that we're considering this this path down will be the global
46:06 optim right again pointing at the system are they're only considering the the left deep trees the bushy plan actually might be the the the global Optimum but they're not even going to consider that the newer modern systems will consider bushy plans but I'm just I'm highlighting the system R1 because that shows you like things you can do to cut down the search Bas because you you can't exhaust look at
46:30 everything all right let me talk about the the top down Optimizer um so I'm I will say I'm to me I like the top down optimization approach better this is what we're building at the new system we're building at seu does this um the the Germans disagree uh and for me this is easier for me to reason about than the than the uh than the bottom up one um but let me go through it and see what you guys think so the idea here is that we start with the logical plan of what we want to produce our output from and then now we do we do a sort of search down Traverse down and start adding in
47:02 the the the physical operators that get us to the approach that we need and the idea here is that if we recognize that at some point of of the of a branch that our best cost we've seen so far going down this Branch or the cost we have the branch going down this far is already worse than the best cost we've seen ever
47:20 uh in in our sort of in our search we know we don't to Traverse down the rest of the branch because at no point it's magically the cost going to get better because they can't do that so this is what Microsoft SQL Server does um and remember the last class we talked about volcano uh we talked about the the B plus tree from the GS graphy guy he's the one that invented this approach in the 1990s he wrote a paper about it it's called Cascades it's inescrutable like it's very difficult to understand um you can't take that paper and build anything with it Microsoft H hired him paid him a lot of money to basically build out their new query Optimizer and SQL server in the 1990s based on this approach in Cascades uh
47:57 and in my opinion now SQL server with things I can't talk about SQL Server probably has now I would say they're going to reclaim their Crown to being the best query Optimizer whereas the German one was the best for a while the SEC server one is getting much better this year but we we'll discuss that in the class next semester all right so what's going to happen here start with the logical plan at the top we know we want to produce the a join
48:19 with artist appears an album we're also going to include the physical property we care about that this data has to be sorted by uh the artist IDE and then now there going be a bunch of rules that we're going to apply that that can convert logical plans to other logical plans like a join on AB can just be a join on ba those are equivalent and I can do that transformation but there's also be rules that convert The Logical plans to physical operators right so a join on a I would convert that to a hash join on a and b as I said before when you apply these rules you don't go from a physical operator back to a logical operator it only goes One Direction but the logical operators can can get swapped around as much as they
48:57 want so now we introduce all the logic operators to build up our query plan so we have the the scan on the artist album appears and above that we have the different joint orders we would want and again soon this gets uh blown out U for all the different combinations that we have so then now we start at the top and say okay well what operator do I need to add below me to allow me to produce this output of a join uh of the three
49:22 tables so I could add the merge join and in this case here I'm doing a a uh I'm doing a a join on the I have some input given to me that's a join on A1 A2 and then I I'm joining with A3 so I have this sort of placeholder here thing to say down below me you're going to join A1 and A2 I don't know how it's going to be joined but it's keep I know that something's going to feed into me that's going to give me that result so you sort of keep track of like what needs to be coming into you in order to produce certain results so then now you come down here and say okay well what below me would give me the join on A1 A2 and feed up into uh the result of A3 right
50:01 so say now I have my my join artist and appears as a logical operator that would feed up into this this placeholder here and then the album is part of the scan of A3 and that feeds up into what A3
50:12 is yes so A1 A3 still like abstract at this at this point here you would have placeholders to say some somebody somebody below me is going to give me A3 as the album table right I don't know how they're doing it but I know they're going to feed up to me right and same thing with the joint A1 A2 something below me is going to give me the joint between artist and appears I don't know how they're going to do it but it's going to come up into me right
50:42 and then now I iterate down here and say okay well what what would I need below me to produce the joint of this well I could have a hash join well then same thing how did I get the data in my hash I have to feed in artist and appears
50:54 right and then do the same thing I could also have a merge join so same thing what's the physical op to this and how what feeds me into that right and as I'm going down I'm doing cost assessments and say okay well how much would be this hash join given that I'm expecting this many tupal coming up from artists and and appears or how much what would the cost of being doing the merge
51:14 joint so now there'll be additional enforcer rules we can apply to make sure that again the data coming in at at our from one oper to the next is in the form that we would want right so in this case here again I my my enforcer rule would say the data that comes at the very top has to be sorted on the artist ID I don't care at this point the very top how it got sorted just has to be so when you have things like a hash joint feeding into it all right hash joint is inherently unsorted so therefore I know that there's nothing I need to consider further down from this physical operator
51:45 because it's it's not going to be stored in the data that I need but then I could have the quick sort feed into me like an order by operator and then therefore by adding that now I I can explore that further but now I can do things like okay if that was being fed Into Me by a hash join and at this point here the the the cost of doing the hash join plus the quicksort is already greater than the the the the the smallest cost I've seen for any possible plan uh complete plan in this this tree I know I don't need to Traverse down further because it's never going to get magically better like you like the cost is always incrementing it can't magically get faster for no
52:23 reason so again this is the pruning thing you can you can do here you can't do that in the dynamic approach programming approach yes does it takes uh does it use that enforces uh from the beginning or just after the it's question is do does it use the enforcer rules since the beginning or Afters it's always in the beginning it's always part of the search
52:47 right I'm just highlighting as as an example here yes how does it approximate the size of like join like if taking a top down approach question is how do you approximate the size of join if you're taking a top down approach
53:03 uh yeah so at this point here You' have to you kind of need to go go to the bottom some cases but then you basically memorize all this information so when you have to go to the Bott at least once and say okay what's the cost of like this path going back up here like how much data do I expect to get out of I'm not showing the physical plans or doing the scans right versus indexes like how much data would be coming out of scanning this table and therefore uh and I store that in a in a memo table and then now when I go down a different path I say right I know I'm going join an A1 A2 have I seen the path down the bottom before if yes I reuse that cost right and then that allows you to short but yeah you have to get to the bottom for at least
53:48 once so the guy that invented this uh Cascade stuff the G graphy uh when he wanted to test a Time award at sigmod a few years ago so he said that the best way to do this would be you do Cascades first to generate a sort of rough outline of the plan and then you would use the dyamic programming afterwards to do the joint ordering so he's actually even though he invented this he said you don't want to use this entirely you want to use the uh the hypergraph approach from from the Germans to do joint ordering and nobody actually does that yet um but to me again I I can reason about this much better than I can about the DP
54:23 stuff all right so we got a lot s a lot to cover uh let me try to get through the n quer as fast as possible just basically just give you a understanding what's actually going to happen and again if you take the the the class next semester we'll go into one more detail n queries are going to be are going to trip us up because they're not really joins right they're these these subqueries that you have to be reason about uh and you know you don't want to do the stupid thing of like for every single tupal invoke the N query over and over again because that would be super slow so what you want to do is either rewrite them to decorate them and flat them down uh to joins or extract out the Nesta query run that once almost like a CTE for the given query and then inject the result into the the call in
55:11 query the first approach is always be better you're not always going to be able to do this uh this is like the fallback choice if if if it's you can do that if it's not entirely correlated or not correlated all right so say we have a query like this we're trying to find a bunch of sailors for reservation you're trying to find people that all reserved a a boat on a given
55:31 day so in here we can identify that the the inner query is referencing a the outer query so therefore I could rewrite this now to exract it out to be a join right this is the best case scenario because now I know how to make joins run faster instead of having run for every single tup in the sailor's table run the inner query I can now just do my join and rip through that very
55:53 quickly right for the hard again you want to break up the queries into blocks just like we saw in system R and try to then reason about what to do with that one block at a time uh and then in some cases again if I can if I can flatten them through rewriting that's great if I can't then I just run it separately as as if if a CTE so an example like this where now more complicated query we now inside this we have a nested query that's producing an aggregation on the saers
56:20 table and we're checking that for every single uh record in in the outer outer query if I can take this Nesta block extract that out now to be a separate function or sorry a separate query again like a CTE now at runtime I run that quer at the top once and then check the Val value there right and that'll run
56:40 fast the the Umbra system and duck DB can do the best at least right now at at decorrelating these these subqueries uh SQL Server is catching up very soon yes if you write CTS in your query say it's like redundant CT like you write a CT
56:56 will a query Optimizer in like modern systems recognize you did that and then like deaggregate that and put it back in or will always comp the CTE and then use that even if it actually is not like you shouldn't have written one this question is if you have a CTE maybe high level what does a d system do with a CTE basically yeah it want to rewrite it as joins that's that's that the ideal case
57:21 um yeah because if it's something like this where there's an aggregation where no matter times you invoke the CTE it's always going to have one Tuple it's always going to just do a join for that right in this example here you could you could rewrite that as a CTE would would produce the same
57:38 result all right another thing we got to care about is how handle expression trees um right the idea again that we have a bunch of wear predicates in our wear claws or on Claws and we want to convert them down to be the minimal amount of work we have to do while still also uh producing the correct result for for the given query and so similar to we can have a rule-based system for uh for for the query plan itself we can have a rule-based system for doing pattern matching and rewriting for expression
58:07 expressions for the this one you don't need a cost model unless you're doing reordering but that's not really rewriting expression tree it's just ordering the the Expressions as you evaluate them um in most cases again I think in most cases you don't you don't need a cost model to do this and most systems don't do that so there's some obvious things you would want to do like impossible predicates like select start from table where 1 equals z you do pattern matching on this to say all right I have two constants with the equal Clause check to see whether they have valued to true and if not you know
58:39 just rewrite them to true or false and in some systems again if it turns to false post and other systems can recognize I have an impossible predicate and so instead of actually just scanning the table looking every single tool and checking to see whether false equals false it just bypasses running it entirely it says you get no result
58:57 more complex things when you wrote functions in this case here this now you got to go in the catalog and figure out okay well the thing you're invoking what function is that and can it ever produce null in this case here the Now function get the current date and time can never produce null and you would know that in the catalog say this function never returns null based on the return type and therefore you can rewrite that as false and then optimize that
59:21 accordingly for other things like user Define functions uh it becomes more tricky you may actually have to run the run the uh the function to see whether it produces n or not um in that case it's just treated as a black box and you can't do any optimizations yes is the overhead of
59:36 checking unary impossible is it worth it considering is what worth it sorry to do this do this optimization yeah considering usually you try to select something your work is not going to be provably false all right your question is uh uh
59:57 your question is is it worth like take the example here is it worth doing this rewriting no I'm saying is checking for that considering no one is any all right maybe you're asking is anybody that's stupid but there is some overhead in
1:00:15 checking all right question there is overhead in checking this now you're you're like micro seconds right to check this so so your question are people write these stupid queries typically nobody would write where one equals zero right and and if you could argue if you write that that's your fault pay the penalty but a lot of times these queries aren't being written by humans they're generated by these different uh these dashboards that are composing the queries and therefore it's like nested nesting nesting at some point if once you start evaluating things down you may end up with a one equal zero and that for and if I have a billion tupal I don't want to check a billion tup says 1 equals zero I can short circuit that
1:00:57 immediately yes I guess my question kind of Builds on that let's say you have like a human that writes very condensed good queries and then you have someone else that just writes like 200 lines tons of garbage and unnecessary things right like after the query Optimizer how close with the
1:01:13 performance see the question is if are they semantically the same Yeah question is um if I if I generate some have if code that generates some query that produces you know some result set and and the the wear clause and the joint ordering whatever it's very verbose
1:01:32 versus the a human written a very tight SQL query how close would the how close would the optimal plants actually be I mean it's a cop out but it depends on depends on the data depends on the query depends on what query Optimizer you're using like for much of the postc it chokes on some really stupid things right like it won't pick index is if you uh like if you do anything like order if you have like a wear Clause with a order by Clause with a
1:02:05 a uh an expression in it it won't pick it like like if you do uh order by ID plus zero and ID is an integer it's always GNA be the same but it sees the plus zero and says oh I can't do that right so there's like it depends on so many different factors it's tough to say
1:02:24 the The Mach I would say that the machine generated queries often are much larger not because they're adding superflous things just because they're being generated by dashboards with uh with very large like uh selection sets and things like that um I can't say who but a very
1:02:42 well-known Cloud company you've all heard of and used uh like they have queries that been coming out that that are 10 megabytes like the seal string itself is 10 megabytes because it's a dashboard with these these massive in Clauses for every single possible combination and so forth right
1:02:58 so you know so the complexity depends on so many different factors it's tough to say what you know you know what tough to say whether it's always going to be one is be better than another because you could argue that that sometimes the more verose you can make things therefore the more information you can provide to the query Optimizer what you actually want but again if your Optimizer is crap it's just going to choke on that yes forer
1:03:21 engine is it more common to process by human or by Machine this question is because are most qu written by humans or machines most qu are written by at this point most machines computers right think about you're on the web page you load a web page as a bunch of seq queries that's all gener by computers
1:03:38 right okay all right there's a bunch of different optimization rules these are two major ones and ob one here like you have a have a disjunction value between one and 100 between 50 and 150 you obviously can just rewrite that into to be a single between clause and then that's much faster
1:03:56 right again there's a bunch of different tricks you can do to figure this out all right so now the last 15 minutes I want to cover uh how are we going to actually do these cost estimations as I've been saying like how do you determine one query plan is actually better than another right so we have all these formulas that that's they going to tell us like s join is going to cost this amount and and hash join is going to cost this amount but now the actual
1:04:22 runtime costs of these things are going to depend on what's being fed into to them right so now to compute the total cost of this query plan I got to not only know how much data I have in these two tables but now I need to know what's the selectivity of these predicates to say how many tupos am I am I going to filter out likewise with the join how much data I is going to get past you know going to get filtered I get past the past the joint operator that then feeds up now to my projection
1:04:49 operator right and now the big challenge is going to be is that Computing these estimations is super hard because we can't actually run the real queries because that would be too slow right we just said it was MP hard I can't run MP hard queries to figure out what the best one is and actually pick that it is kind of what mangad B does mangad DB just runs all the queries and see which comes back first and and that's that's what they pick uh for joint if you have no joins that's fine uh but for joins you if you you know the the number of possible ches you could have would explode it' be a bad idea right and the problem's going to be as we see as go along like this lecture is kind of a downer because I'm going to tell you here's what you can do and here's why it sucks and we don't really go into how to actually solve it because you know
1:05:32 because it's not solved but it's basically a house of card so like if I have crappy estimates coming out of this thing and I feed that into this and I have crappy estimates coming out of this then that feeds into this and I have crappy estimates coming out of that even further it's like it's like crap build on crap build on crap and Beyond three joins all this sort of sort really starts to fall apart
1:05:50 right but we again well try to get through it okay so uh again we're use this cost model we have that's going to all us to predict the behavior of the query plan for a given database State meaning what the hardware looks like what the data looks like and what the the the the configuration of the system looks like and we'll produce some internal cost number that tells us say one query plan is better than another because it's simply too possible to run
1:06:13 everything and what the cost is going be apprised of is a combination of physical costs that says here's how much CPU time I'm going to spend or here's how much IO I'm going to use or if you're really fine like here's my number of cash mes I would expect for one operator res another um and you sort of aggregate them weight them you know a CPU cost more than disc and so forth right that produces some number and then you can combine this also now with the logical cost that says here's the number of uh tupal I expect to come out of this operator here's the size of those tupal like the number of columns I have
1:06:46 because again that helps me figure out whether I want to do that early projection um and then I could feed that into the next operator and say okay given this input what what it's output of the next operator so the most systems will do sort of a com be a combination of the two of them the highend Enterprise systems will do more the first one like postgress will do mostly just IO cost uh I think SE is the same thing but like db2 when you turn it on it runs bunch of micro Benchmark to see how fast your CPU is how fast your disc is how fast your network is and uses that as the constants to fill in for uh this phys physical cost calculations
1:07:26 using p as example they just have this notion of I have CPU cost and I have IO cost and the the costs of them are relative to each other same thing with squential versus random iio the cost of them are just relative to each other so there'll be some magic values or parameters you can set to say you know sequential page cost
1:07:51 the default is one so now random page cost will be some multiple of of this right same thing for CPU right going back here I think they said CPU is uh if if you say memory is four 400x faster than reading from dis and then squential IO by default is 4X faster than than random
1:08:07 IO right and if you go read the documentation they basically have this big warning here and say like hey look like these are just you know magic constants you got to figure out how to set them correctly if you want things work right um but of course and adjusting them can you know end up producing widely different plans that may not be the best thing that you want
1:08:26 they can drift over time obviously is your is your if you're having SSD ssds actually get slower as you fill them up more right because they has there's less room for the garbage collector to move things around so what might be the best uh parameters for these things when your disc is basically empty will change when your disc is like 90%
1:08:45 full right again this is why the commercial systems try to run micro bench Benchmark to figure this out all right so now again how do we how do we then try to estimate what what the input output are are going to be for these different operators so that we could then use something like a physical cost estimates to say here's how much work we plan on doing so as I said before there'll be there's a catalog
1:09:07 that every D system is going to maintain that has a quer Optimizer that's going to be that's going to maintain statistics about what data looks like and then use those statistics about to estimate the selectivity of different predicates uh in different operators to then say how much work is going to be done so most of these systems will maintain these things in the background for you uh but you can trigger them through the through these SQL commands like analyze or analyze table or update statistics like this causes basically a query to run in the background that does a sequential scan over your tables and F and then computes whatever whatever internal representation they have about about the information whether it's histograms or sketches and so forth
1:09:45 right like in in in Oracle I think it runs at like 9 p.m. or 11: p.m. every night this thing will run as a as a Cron job and recompute all you know new data for you and post Quest I think it gets triggered when like if you have a table if you update 20% of it then it gets fired off or the vacuum runs the vacuum can also maintain St statistics as well so let me give one example of how we actually use these statistics to then compute estimations and there's obviously going to be different formulas for all these different kind of you know less than greater than so forth that you can use but let's do the most simple one of like something equals
1:10:19 something so we're going to have a notion of a selectivity on a predicate right the predicate is where AG equals 9 and that's basically be what fraction of the tbal we expect for a given table are going to qualify qualify or satisfy that predicate and therefore would be produce as output uh for for a given operator all right so if we maintain a histogram of like for all the people we have in our database their ages we basically want to say for the number of currents we have and the number of stinct values we have for the predicate
1:10:44 this age equals 9 we would just jump to this offset here and say well the cardinality of H equals 9 is just four because we have four in occurrences across the entire table and therefore the selectivity is predicate is if I have 45 tupal 4 over
1:11:01 45 right so I can do that and say okay for for given wear clause on a scan even though my table has say you know 45,000 I'm going to get four tupos coming out of it as part of this predicate then now I can use that to determine join ordering because I if I apply the filter first because i' I've done the predicate push down now I say after I do my filtering how much data do I expect to come up uh from from this table and feed into my my joint operator
1:11:27 and therefore I can use that to determine whether one is larger than the other to change the joint ordering something equals something that's easy something equals something on a unique Clause oh that's the best right because that's that's the easiest thing to do it's when you have non-unique values and then non non equality
1:11:44 predicates right a non equals would just be reverse of this that's easy it's one minus the the calculation all right so seems easy right what's the problem well this in many cases you're going to assume uniform distribution of the data all right uh for Heavy Hitters you can set them set them aside like say the top most the top most frequent values I'll have exact counts for those but I don't want to store a histogram for every single possible value because if I have a billion records a b billi one billion unique values I don't want to store one one one over again that I've seen it one time right you so you start collapsing things down or aggregating things down to make these things more tractable
1:12:25 another big assumption that lot of sys are going to make is that they're going to assume that the predicates are are independent right again thinking back your statistics class if I have something equals something and something equals something I'm going to assume those two predicates are independent and therefore I just multiply that their probabilities together to produce what I think is the global probability but that's not always the case and the last one inclusion principle just means that like if I'm doing a join I'm going to assume that when I join into another table there's going to be at least one key exists in that other table to do my match which isn't always the case
1:12:57 so just really quick I want to show where this always goes bad uh with this example here same a database with uh keeping track of cars right every car is going to a make in a model and so I have 10 makes and 10 models or sorry 100 models so I have a predicate like this we making equals Honda and model equals Accord if I make that Independence assumption and uniformity assumption it becomes
1:13:17 terrible right because one Independence would assume that there's there's a card called a chord but it can be made by different manufacturers but that's not true we know Honda is the only one that makes a chord right so if I assume they're independent I take one 10 and and one over 100 multiply together and that that gives me what the the estimation is the selectivity of this predicate but the true estimation is this so I'm off by order magnitude just for this like simple example because I assume that they're
1:13:46 independent so the there's these notion of correlated statistics you actually some STS you can tell them I know these two columns are correlated therefore don't compute their statistics separately compute them together but you as a human or the operator of the system have to tell the day system what these correlations are it doesn't figure them out for
1:14:04 you yes are systems that handle this say say it again are there systems that we learn like if you query very frequently make and model at the same time it's start like Computing correlated statistics this question is are are there systems the smart that recognize that if I'm Computing make always and always again in the same wear Clause therefore don't treat them as separate predicates or independent predicates compute correlated statistics for them the highend sys might but I don't I don't think so Oracle might I don't know the others what's that I just said bust bust there's no I don't think we I don't think we even have statistics
1:14:45 um we'll see what project for I don't think it does okay all right so this is a bit of a downer page of just try to say that like okay this gets really hard all right so how do you actually can can can calculate these statistics what are we going to use so the three choices are either histograms sketches and sampling I want to blaze through these real quickly just show show you that these exist and the problems they can solve um you know it's not something I would cover on the exam because I just want to be aware of like when you get a cost estimate where is it actually coming from and it's going be the the combination of these three choices some systems do all of them some systems only do some of
1:15:18 them so the histogram we saw before again we just assume that there's for every single unique value we have the number of occurrences but obviously again if you have a ton of unique values then this could be really expensive right to store a count for every single value so what you can do is you can aggregate them together uh using what's called an equi histogram and the idea here is that you just have these bucket ranges you say between one and three I'm G have one count uh four to six I have another count and so forth and then now your histogram is basically aggregated
1:15:48 together and I can reduce the number of counts I have to store or now the challenge is going to be like if I have a you know a unique value right say I I'm trying to look up you know 5.5 it wasn't really my original data set but it would land in this bucket and I may be overestimating the number of tools that I actually see in there but again the alternative is distorted and is that count for every unique value and you can't do that so this this reduces the size quite a bot the alternative approach is do equid depth histograms
1:16:19 and the idea here is that the the size the range size of the buckets will be variable I just want the counts of the number of elements the count within that bucket to be the same so this first range will be 1 to five the next range is from 6 to 8 but both cases the count is equal to 12 so again same thing I'm reducing the number of um of unique counts I have to maintain but again at at the cost of
1:16:44 accuracy going back to project zero you're asking about hyper log log I answer the question like what was that actually being used for well you can use this for now cost estimations in your query optimizer right the count sketch was the other one that we talked about basically there're these problemistic data structures that can give us approximate counts for the the number of elements within some range or whether this value exists or not and we can use that now to to improve our accuracy of our
1:17:10 estimates you can do this a combination with the histograms or some systems you get rid of histograms and use these sketches entirely or because there sweet of sketches you can use that have the different properties that you would have in
1:17:22 histograms another approach to do sampling now I said before like oh it's so expensive to run these queries you wouldn't actually want to run all of them but you kind of do a little bit of this with actually sampling but not every system does this the idea here is that you collect some subset of of the original table uh into this sample set
1:17:41 and that's just stored in the catalog or St in the D as if it was another table it's like a local copy of this and then now when I want to do cost estimat for predicates I'm not running the full query I'm just running like a sequential scan on my sample and now that's going to give me a better estimate of what the actual selectivity is so say I do a random sampling here of this table right
1:18:02 and then now when I want to evaluate find me what's the number number of people I expect to have or what's the average age of people where the age is greater than than 50 well now if I take my predicate here and I apply it to this sample here well onethird of them are going to match so now I could use that to say well the selectivity of this of this predicate is one is be 1/3 and then based on that I can determine whether it makes sense to go look up an index if I have one or do a squential
1:18:29 scan right there are some systems that actually would would use the samples to produce the actual answer of the query you can do approximate aggregations uh but again that's that's explicit you have to call that in your SQL statement most systems won't do that for you
1:18:42 automatically okay all right so again this is super hard we barely scratched the surface I'm just kind of like a the smoker SP just a brain dump up like here's the things you have to consider when you're building a quer Optimizer in a Davis system and you'll see this in uh in Project three you have to touch the query Optimizer a little bit to do do your queries but they're not cost based I think it's just rules but a high level what we're doing is going from a SQL plan sqle query to a logical plan to a physical plan and that physical plan could be either cost based
1:19:09 or it could just be generated B based on rules different optimizations we can do to evaluate the Expressions try to flatten the nest of queries and so forth and then our cost model estimates will come from summarizations that we collected from looking at the real
1:19:22 data so if you like this kind of stuff and we make a lot of money going to Industry again we're not teaching 721 next semester we'll be teaching a special topics course on 799 and that'll just be entirely on credit optimization
1:19:34 and I guarantee that like I guarantee but like you will have no problem finding a job if you do well in that class next semester okay any questions yes I had a question about the histogram stuff go go for it yes should we update it every time a wased deleted or only a fix siiz interal for all right question is for these histograms when are these things actually updated
1:19:55 you would either do it time based like every 12 12 o' every day run it or or a uh like when 20% of the data has changed then you run it because otherwise to S to maintain all right so uh next class we're transitioning on to a new topic on on transactions current control this is the second hardest part of data database systems creation the first transactions the second because it be challenging to reason about correctness when like things like the order you submit queries doesn't have to be the you actually run them and that's okay okay I need something refreshing when I finish manifesting cold whole B like Smith and Wesson one court and my th's hip hop related write a rhyme in my pants
1:20:38 intoxicated lyrics are quicker with a simple lier since I'm a city scker play Waves a pieres I create rotate at a r too quick to duplicate feel a breeze at escate mik's at Fahrenheit when I hold it real CH then I'm in flight then we we ignite starts the boil I heat up the party for you let my girl me my mic down with oil Rec still turn with third deg burn for one man I heat up your brain give it a suntan so just cool let the temperature rise to cool it all with
1:21:11 odds [Music]