CMU Database Group · 1:14:22 · https://www.youtube.com/watch?v=MFazkaZKs1s
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 okay it's 2 o' all right let's get let's get started we have a lot to cover today um so again administrator s the midterm exam should be no surprise for anyone is this this Wednesday two days from now in this room at the same time uh I think everyone who who who needs accommodation say email me if you haven't yet please do that and then the study guide is available online along with a practice exam um project two will be due after the fall break on Sunday October 27th but we be holding
1:00 recitation this Thursday at 8:00 p.m. on Zoom we'll announce that on on Piaza uh and then that'll be recorded and we'll make that available on Patza afterwards as well okay who here has started project two okay a little bit okay again I realize there's other exams there's other uh be on this class but you should really get started on Project two that way because it's not going be easy and uh you know you show the recitation ask ask harder questions
1:28 okay all right Beyond this again we have some uh some Davis clocks coming up today at 4:30 on Zoom we have parade DB they basically took postgress stuck data Fusion inside of it first got rid of that now they put duck DB inside of postgress uh and then they have this thing called tantivy which is a sort of like Lucine when we talked about full teex search indexes they put all that inside a postgress so that guy's giving talk today um and then the when we come back from fall break there's another startup called spice. a and they have put data Fusion they're using data Fusion to do llm stuff I think uh and so
2:06 the beginning with talk and then I'm assuming you pronounce this as Exon uh they're giving a talk uh about their tool using data Fusion and the end of this month if I had to vote for one database startup to get sued for uh trademark infringement it'd be the these guys right uh I don't think I don't know if Exxon Mobile is as La tious as Disney but you're asking for it right so all right that's not our problem though that's his problem okay uh any questions about the midterm any questions about project
2:37 two all right so let's jump into this I mean I say this every class like uh oh this is going be a great lecture but this is going be a great lecture because it's joins it's super super important um so last class again we started talking about how we were going to implement algorithms inside of our database system to start running queries right to start processing data to do essentially the relational operators that we that we we want to support uh to to you produce results for when people send send us queries and one of the key things that we talked about which is getting the theme of this semester is how to support
3:09 data sets either intermate results or the base tables themselves as we're scanning them that are larger than the available memory that's that that we have in our database system and one of the techniques that we we used last class and we'll see this over and over again throughout the entire semester uh is this approach this or this pattern called divide and conquer like breaking up a hard problem to smaller problems meaning breaking up something that that doesn't fit in memory uh into smaller chunks that do fit in memory and then divide that up and then slowly merge it back together to produce the final result and and we'll see the same strategy used today when we start how talking about doing hash joins if the H you know if the data set doesn't fit in memory how do we handle that and then the other key thing that we T discussed
3:49 last class is that we started off talking about external merge sort uh sorting in a datab system and we showed how we can use sorting to compute aggregations but then we also started talking about how to use hashing to to compute aggregations as well so we're going to see the exact same thing today we're going to see different approaches to do joins one will you know one will be Bas based on for Loops one will be based on sorting another will be based based on on
4:11 hashing right and these are basically the two main choices you have whenever designing a you know data intensive algorithm am I going to do something through sorting am I do something through hashing and we as we go along we'll see the pros and cons of each of each of these but in general the spoiler for this lecture is going to be hash joins are almost always going to be the better choice the the faster choice but we'll we'll we'll we'll go through this to understand
4:35 why all right so should be sort of obvious at this point in the class cly if you did homework one why do we need to join well in the context of our relational database system there's this technique called normalization which we didn't discuss because I'm trying to how this I don't think you need to know about normalization other than to know that it exists uh a prior version of this course you used to teach normal forms it's basically how do you take a table split up to to smaller components like through keys right think of like
5:02 the the first normal form is like I put everything one giant table and then I can split it up and break and break it up to you know to to C reference tables Dimension tables that we talked about before right that's called normalization and there's a whole Theory uh uh background on it that you don't need to know because nobody uses that in the real world so I'm saving you from that but since we know our our our our our databas can be brok up to smaller relations smaller tables we obviously want to join it back together oh go get Andy's account and get all his orders well that's join between the order uh order table and the account table right over some over some key so this join operator is going to be going to be the mechanism is the way that we can
5:39 reconstruct the sort of full Tuple or his original Tuple or for the the full entity that we're trying to expose in our application the joint is how we're going to be able to stick these things back together and we want to do this in such a way that we don't have information loss meaning if I join I want to join Andy's account with Andy's orders I don't want to miss some of Andy's orders right I want to have the exact
6:01 answer so that that's the goal for today the type of Al we're going to focus on in particular is going to be called a inner EO join so inner join just means I have two tables I'm doing uh an exact match on them and the equo joint means I'm the the join predicate is just going to be equality right you can do less than greater than there's things called anti- joins where something is not in something right the at a high level some of those algorithms will be the same
6:30 um but for for Simplicity we just focus on inner Echo joins and I I'll talk briefly how we can extend that to to left like left outer join most joins in the real world are going to be inner equo joins right most of the time like when you when you write queries and applications it's going to be inner joins inner equo joins left outer joins are probably the second most popular one um and anti- joins and and semi joins these are like special case things we'll cover
6:53 later so the other thing to understand is that we're going to focus in this class on binary joins meaning mean we're only going to join two tables at a time now the query May reference multiple tables you know three or more but the algorithm we're going to algor we're going to talk about can only take two tables and then join them together and if you want to join another table and you take the output of the first join
7:14 and you run the same join or the the same binary join algorithm on on on you know on the output with another table there are techniques called multi-way joins uh these have existed in the literature for a long time because it seems kind of obvious I want to join three tables why not join them all at the same time uh but in practice nobody implements them because uh the performance can be can be variable like Microsoft added this in SQL Server I think like 19 1998 they took it out in 2001 because depending on the queries depending on the workload the performance could be all over the map so again most systems that you can think about uh that you know of are going to be doing binary joints that we'll talk about today there's another more modern category of joint algorithms called worst case optimal joint algorithms this is these are when if you're doing like graph traversals like think of like a a network
8:04 uh representing a graph structure like a uh like a social network um these are rare uh there's only a few systems that I know about umbrella Cedar DB out of Germany uh and then uh that relation AI people that came talked about four they have a worst case opal join algorithm these are special case algorithms I suspect they're going to become more common in the future uh and we do teach these in the advanced class but for this class we we don't need to know
8:32 that another big thing that we're going to that we'll sort of lightly touch on today but what we'll we'll talk more about this after the sem uh the the fall break um is deciding what in what order we should join and actually what joint algorithm we should use and this is what the query Optimizer is going to do for us and we'll cover that again after after the fall break the idea is that I I say my SQL statement I want to join these two tables I'm not saying what I want join you joint a versus b or B with a and I'm not saying what joint algorithm I should use S join versus hash join or whatever so all that's going to be abstracted away the cost model and the optimizer will take care of that for us but in general as we see as we talk these algorithms the rule of thumb is going to be we want the the the left table we call the outer table I'll explain what that is in a second that that should always be the uh the smaller
9:21 one and we're going to do this for performance reasons and again when we show the algorithms you'll see this so we saw this last class again what what is a query plan uh it's always usually represented as a tree uh it's usually usually uh implemented as a tree some systems can do it as a dag tree is obviously a special case of a dag you want to use a dag if you can but most systems don't again the idea is that the data is going to flow from the bottom to the top going from one oper to the next
9:50 right and then the output of the query is going be whatever the the whatever the root node spits out for this right so in this example here we see we have the join on and S right we're getting uh data from R up into this and then s goes through a filter first and then it goes into the join We join that again this is a logical representation of the plan I'm not specifying what the what this joint algor actually is I'm just saying there there is a
10:15 joint and actually at this level too you're you're not even specifying what is what is the inner table versus the outer table we'll see that in a second so there's two decisions we got to make one is what should be the output of our our joint operator and we talked that before like late materialization early materialization we I'll show an examples of this more more detailed and then the next thing we got to worry about is how are we going to determine whether one join algorithm is better than
10:43 another I just said that oh you typically want the smaller table to be the outer table like on the left side of the tree it usually has represented uh but the how do I know if I'm joining three tables which two tables should I join first and then the third right so we need a call model we need to wait to understand which one is to be better for
11:03 us so in case of the first decision it's that again late differ realization versus early materialization so no matter what joint algorithm we pick like what physical implementation of the joint operator we pick the output is always going to be the same meaning joining RNs in this example here it doesn't matter what I'm doing a hash join versus a a start merge join the The Logical output is the same mean that the tupal the unordered tup will be the same
11:28 now there maybe physical properties that I'll care about later that will be different like sort mer joint will come the data will come out sorted right because you have to sort it to in order in order to do the joint whereas hash will be more random for that we we can we can ignore that for we can ignore for now um but there's other design stations we we'll cover the midterm as well is like are we sending out one tupal at a time every time we invoke The Joint algorithm or is it a batch of tupal or all the tupal uh where if we have to spill a disc where does that go right so the output we could be logic will logically be the same but physically it might be different depending what algorithm we're using but again for this class today we don't have to worry about
12:05 this so this is just a rehashing what we talked about before the difference between early materialization and late materialization remember early materialization the idea is that I'm going to construct the entire contents of the tupal at the moment I retrieve it from whatever the source of data that I'm getting it from like a table or a file or some some network storage right
12:24 so if I take this query here I'm joining r with with s right I'm going to produce the The Logical output which should look like this right here's R and all its attributes here's s and all its attributes right and then now when I compute this joint in the
12:42 query right this whole thing is going to get from you know from this operator computes to this and then that gets fed up into the operator above it which is a projection which is going to throw away the stuff that it doesn't need right and in this example here because I got the entire contest of the tupo at the bottom do the joint and then that join basically mashing the two things together and that's going up the query plan the the upper operators in in the query pen never have to go back and get more data right things are just pass along from one operator to the
13:15 next so in light materialization the idea is that at the moment you retrieve the data from the underlying uh you know data source you get the bare minimum you need at that moment for that given operator so you can be a bit clever here and say okay well I know I'm going to have to do a join later on so I don't need to bring in these other attes like name and then value and and date I'm just going to bring in the ID and then I store the record ID that corresponds to where this tle came from and then that's what gets passed up from this joint operator
13:45 here right so again if I think I have a thousand columns or even something larger than that then I'm only I'm not passing around those thousand columns for the two tables as I go up I'm just passing again the bare minimum so then when I get to this projection operator here it then has to say okay well I know I have these two tupal coming into me and I I need to go get the the date field from the S table so I'm going to use the S table's record ID to then go fetch whatever the pages are that has that that that date and then and then fill it in yes so like Pro why
14:17 don't yes so question is why don't you propagate What fields you want at the bottom and then when you do the join pass them along that's called projection push down yes we'll get to that later yes but that that is a classic that's that's the you would do for this yes but again it actually depends on like yeah so so what he's proposing is that going back
14:38 here right I know I'm going to need the customer date so at the moment I do the join instead of just throwing away the customer date go stick it in as part of the tupal right and then do the join and pass it up so again depending on how your your query plan is implemented do I have the tree here right this could be over the network right and then your to do the scan and then you do the filter on another machine so maybe I don't want to pass over the network the customer date cuz it's it's going to get filter later on so maybe I want to do a another retrieval here before I do the join but then I might as well just do it afterwards like there there's all the different n decisions you can make uh
15:15 we're not there yet but it's not as trip as like oh I know I'm going to need this let me pass it along because again I may be passing a billion Two bows and filter down to just a two and I'm passing along customer date and it was a waste
15:29 this stuff is like like figuring what you the bar you need to do the minimum amount of work is like super hard because be honest your statistics are going to always be wrong so you're making guesses on bad data which is
15:39 hard or obviously prone to error okay so this is common in the column stores because uh if your columns are you know the different attributes are stored in separate files why go fetch those files just to Stitch things together only go get them as you need
15:57 it all right and then The Other Des station we talked about is how we actually determine whether one algorithm is better than another right and so say again we're going to use this query as our running example throughout the entire lecture joining R and S on a simple ID lookup R ID equals S ID I'm not saying whether R I think we actually s r ID is is the primary key and I forget whether I don't think S ID is but and for our discussion today it doesn't
16:20 matter but the the variable going to use to understand the cost of doing these joins are going to be this MN and R uh Big M and Little M big M and little n so and it be M little lowercase two plus an R PES in N pages in in s so that for this class and this lecture actually for the rest of the semester the cost metric we're going to use to determine whether one joint operator is better than another is just going to be the number iOS we have to use to compute The
16:55 Joint right so we going we're going to ignore what's the cost of actually be writing out the result if you have to spill a dis right because to be honest that's going to be the same for all our joint algorithms as I said The Logical output is going to be the same they're always going to produce the the the same X number of tupal as their output so it doesn't matter what you're doing one Alor another I got to spill out the disc if I have so many Tu and run run a
17:16 memory we're also going to ignore the computation and network costs for now uh obviously doing the nested Loop joint we'll see in a second is the easiest thing to do and has a low CPU cost because you're just just doing a loop for bunch of for Loops um whereas a hashone you got to Hash something and find a location and depending you know what hashing scheme you're using you got to scan through right that's going to be way more competition expensive but we're just going to assume that the cost of going to disc is so much more than any comput computation we have to do
17:47 especially our hash sh is going to be very very well optimized we we can ignore that the network cost were also avoid as well because again at this point in semester we're still assuming our databas system is running on a single box we'll talk about just distributed queries later on but like you could do a joint across multiple machines and now you got to figure out where the data is where do you got to move it to and that certainly is be expensive but again for today we're ignore that so it really comes down to how much IO do I have to do and then to simplify all sort of discussion we're going to assume that nothing is already in
18:16 memory because again you can't account for that in your calculations like because depending on what other queries are running at the same time how much memory you have and and so much other factors you can't you know that's a moving Target it's hard to calculate so for our purposes here we'll just assume that everything's on disk and what's the cost of bringing things in and then we have to Spill the dis writing back
18:35 out okay all right so here's the menu we're going to discuss today so we're going to first talk about the N Loop join which is the most the most simplest thing you can do then we'll see how we can then do sorting to do sort merge join but then we'll spend most of our time at the end talking about different variations of doing hash joins right because again these will be the most important uh most important thing to do if your system is trying to support an uh transac
18:58 workloads or o workloads as we talked about before you typically Implement index Loop join the one at the top because it's like again going get Andy's account record that's going be one tupal and Andy's orders maybe 10 tupal and you'll have an index for those that's going to be super fast hash join is going to be too slow for this but if you're doing analytics of olap uh workloads like deriving new information from the data you already have you're going to you're going to want all of
19:23 these and then the high-end systems will support all of them uh postc can do all all three types of joins hash joins joins and loop joins I think my sqo added hash joins about five years ago for a while they couldn't do that I don't I don't think they can use sort mer joins I certainly like snowflake uh data bricks and and red shift and all those big the big olap Cloud systems they can do all these things I think duck DB can do all three as
19:48 well okay so let's start at the beginning let's most simplest thing to do naive n Loop join we'll see why it's stupid and then we'll build from there so okay this is the query we're going to Target joining RNs so the naive Nest Loop join is just two for Loops hence the name nested Loop and all you're really doing is just looping through all the tupal in in table R and then for every single one tup in table R Loop through all the tupal in table s if they match on our join key like R ID equals S ID then we're going to emit them as our output
20:24 and I have this emit function to say like this thing has been qualifies The Joint predicate and it goes off you know goes off to the next round next operator I'm not saying what what that physically looks like just yet we'll cover that later so I've referring this langine between inner table and outer table now you understand where this comes from it's like when you use this term in terms of joins right it has to do with the loops right the outer for Loop is called the outer table and the inner loop is is called obviously the inner table and in most systems they would represent in the in the query plan the
20:55 this is to your left the the the table on the left of the joint operator is considered the the outer table and the the one on the right is considered inner table some flip this I think snowflake flips this uh and then I think uh SQL Server puts it on the side makes it horizontal but in general you say it's the outer table typically people understand that to mean the the right the one in the
21:17 left okay so I got to put this marker up don't do this this is stupid why you've got to look through the second table a lot of times he say got to look through the second table a lot of times and furthermore we're not even taking in account that we're not storing data as as single records They weide of
21:39 pages right so this is basically saying for every single tupal no matter in the addou table no matter what page it's in Loop through all the tupes in the inner table and then go get the next tupal in the uh in the outer table and just you know fetch that page again potentially and do the loop all over
21:55 again right so again it's obvious for every T in we're going to scan s once right and so the cost for this going back to the the the nclat the syntax we using before the cost is M plus M * n the plus m is because we got to scan all the pages in the outer table once uh and then we're going to scan all the the the pages the big n pages in the inner table
22:19 Little M times so for every single tupal in the outer table we're going to scan all the pages in the inner table again assuming there's no caching nothing in a buffer pool right this is uh it's a very Navy
22:33 implementation so we turn these these these these variables into numbers we actually can see why this sucks and then as we get better how much how much faster we can make things so say the table r m right R has a th000 pages with 100,000 tupes s has 500 pages with 40,000 tupes like not not that big at all right and then if if you plug and chug these numbers in uh to take you know taking the formula we see that we're going to 50 million ios's just to do do this joint for these two tables
23:04 and let's say we have an SSD that can run you know in in 0.1 milliseconds per per fetch right it's going to take 1.3 hours to compute this again we're ignoring you know OS could be caching things hard could be C ignoring all of that just assume it takes for every disc iio 0.1 Mill seconds this simple join takes an hour
23:28 all right well what if I do the thing I said before that you always want to have the smaller table be the outer table so what if I flip that RNs make S be the outer table now we cut it down by 10 million 10 million ios's but we're still in 1.1
23:44 hours right this table's super small right I'm showing abstract numbers but assuming we're doing four kilobyte pages right this thing's 6 megabytes that's going to live in L3 cache on your CP C that's nothing again hardare is going to be a bunch of caching and like it's not going to be as this this bad but like if you just do the stupid thing and say I got a single tup at a time it's going to be terrible
24:12 yes the question is why why do we add Big M yeah this question is why do we add Big M so going back here right so I my my algorithm is for every T in in the outer table so that's that's R go fetch every single page once
24:29 then for every single page then I'm going to go fetch all all the s's pages every single time all right so this sucks but again we know that the database is going to represent or store data in in blocks or pages so we can take advantage of that and do what's called a block block nested Loop join and the idea here now we have a bunch more four Loops where they have the outer loop uh the top Loop is getting every single block in R the inner loop is going to get block and S
25:00 and then now you just do the the inmemory inmemory for loops on those on those two blocks for M SLE to inside them and check to see I have a match all right so now the algorith is better because now we still have the big Big M as the cost in the beginning because I got to scan every single block in in uh in the outer table but now I only scan the the inner table Big M times because for every single page in the outer table I get all the pages in in the inner
25:31 table in this example again we are assuming that we have one frame for the the outer table one frame for the inner table we obviously have a lot more uh memory available to us so we we can do better
25:43 here yes andage question what sorry is BL and Page the question and Page the same thing yes I think I said before like like block and Page are roughly the datab system might call it a page on internals but in hard might call a block they're basically syon those
26:05 y all right so again for all these algorith we're want the smaller table to be the on the Outer Outer table because that means we can try to keep that in memory as much as possible right um and the way we're going to calculate this is based on the number of pages we we expect to have sorry number of pages we do have for our tables and not the number of tupal that we would have for them remember again the D is going to maintain a bunch of metadata in the disk
26:31 manager about or the page directory about for a given table here's all the pages I have for it some of those pages might have fre empty slots well that still doesn't matter when I'm doing my join because I I may go get a fetch to go fetch a page and it may be you completely empty except for one Tuple I still had to go fetch that page it doesn't matter you know how many tubos I actually have it's it comes down to be the number of pages I have that's what really matters at this point here
26:59 and I said we can be clever and say okay well I know I have a bunch of buffer buffer pool frames I can use for this so I can use B minus 2 Pages for the the outer table because again I want to try to get the outer table as much as memory as possible to read that in once and then I have to have to go back and read it again and then I would use one page for the the inner table because I I can only do one examination of a page at a time we're ignoring parallelism here and then I need one page for the buffer for the
27:30 output right so you just change the setup like this right I'm getting B minus 2 Pages for for the outer table one page at a time for the inner table and then do this again and as I said block and Page are the same
27:45 thing so again we go back to our our situation or hyp hypothetical example before now the cost model is going to be Big M plus the ceiling of M m/ B minus 2 because it's the the maximum number of pages I can get in B minus 2 blocks or buffers and to multiply that by Big N because that's again for all those the pages uh so the batch pages I get for the outer table I have to go fetch all the the inner inner tables
28:11 pages so now our query they have before right now we can get it down from I think we had 40 million ios's for the the the blocked Loop join or sorry 40 million iOS for the naess loop join switching uh the the outer and the inner table now I get it down to 1500
28:29 okay well this is actually more realistic now right and I I can keep this join in uh 150 milliseconds that's reasonable not great but reasonable so if we sort of change change the parameters of what B actually is uh you know say 102 pages right now now this calculation has has come into play now we get it down to the 6,000 iOS or switch the outer the outer in the inner table and we get down to
29:05 5500 so what am I intentially doing here I'm basically doing a bunch of squential scans on the uh on the or try to squential scan the outer table once and then for each set of sort of batch of pages I can bring the outer table in I'm do another squential scan on the on the inner
29:22 table sometimes that might be the best you can do that that that' be good enough it can if the data set is small but us usually again usually you do do not want to do this algorithm all right so this is basically repea what just said right the reason why it's bad is again you're just doing much of Loops over and over again and
29:41 blindly searching almost like a needle and a Hy stack to try to find a matching tupal between the inner and the outer table but again the problem we have is again the scans but if we have an index that already exists on the table then we can use that on the inner for the inner table and then now we just do a scan on the on the outer table a sequential scan and just probe into that index to find the the match that we
30:08 want then now we we don't have to do the the sequential scans over and over again on the inter Loops so if you have an existing index you can do this some ssts will actually build the index on the fly so SQL Server does this they call it spooling indexes so it says I really would wish you had a B+ tree here to compete my joint so you know what I'm just going to build it right now so sentral scan the the enter table one build the index probe it for for you my join and then throw it away once the query is over SE Ser I think it can even come back and give you hints and say hey look I keep keep building this index to do this join you probably should build it for me or tell me to build
30:42 it yes build IND his question is when do you actually want to build an index on the Fly and throw it away well we'll see this in a second this is what hashjin does right uh but the I said if if the the data system can recognize oh I'm I'm the best thing for me to do right now is is a index Loop joint because you can you can calculate things like hypothetically if I had an index this thing would cost this amount to build and you can compare that against a hash joint C joint and you say okay even though I still to I have to build this index it's going to be cheaper for me to do this than doing the the naive n loops scans or even the blockness of those
31:30 scans right so so the D will have some notion about uh how much data you have what the query wants to do and it can make that decision for you we'll cover that after the the midterm it's hard all right so index next Loop join basically replaces the inner loop now with a probe to this some index and I'm just calling this index I'm not declaring whether whether it's a hash table or a B+ tree or try it doesn't matter we have a way to do a a point query lookup to go retrieve a you know a single tupal or sorry for a single key go get the one or more tuples that match for it and then for each of those that
32:10 match uh you may do additional qualification then you would go ahead and Emmit it right so you may be the case that your your in this example here it's joining r r ID with Sid so we have an index on Sid so it's an exact look up to go fetch that one tupal or the the the the one T but it may be the case my joint clause also has additional predicates and the index doesn't doesn't have any information about those other attributes in my joint Clause so I still do the probe and the index get the T get the the the record ID go then fetch the Tuple then do the rest of the The Joint evaluation and if then it matches then produce it as my
32:48 output so now our cost is going to be M Big M plus Little M * C and C is just some constant that says it's the cost of probing the index right if it's a B+ tree it's going to be a log n uh if it's going to be a hash table you know on average
33:06 01 right but we can't account for that because we don't know what the index actually is in in sort of theoretically theoretical analytical evaluation right now right so again Big M to scan all the outer table uh but then for every single tle in the in the outer table go do that
33:26 probe all right so what of the main takeaways for n Loop join it's a building block we can use to to to start doing more complex joins um in general we're always going to to put the outer table to have the smaller table of the two we're joining be the outer table and we try to put as much as the outer table in memory as possible to reduce repeatedly having to scan
33:47 it okay all right so in the ex with the inex N Loop join we have a data structure available to us find the exact matches that we wanted right and that's part of the problem with the Nessa Loop joint without that index you're just it's just sequential
34:06 scans so with sort Mar joining the idea is that if I sort my data from my two tables I'm joining on on the on the on the join key then I can walk through and scan those those sort of results and I know in some cases I never have to backt track cuz as I'm going down scanning down I know that there isn't going to be some key on the intert table down below that's going to match uh you know match on the other side and I you know I I may have missed
34:35 it right so the idea is that we we sort everything ahead of time and then that simplifies our scan to then eval allow us to not have to hunt and Peck and try to find the thing that we're looking for to do the joint so this I say in last class there's the external merge sort algorithm we talked about last class and you can use that in the external sort merge joint algorithm so you would use external merge sort in the sort phase of the mer the sort merge joint algorithm
35:02 doesn't have to be exal merge sort it could be quick sort or whatever your favorite sort is right but you sort in the beginning and then you do the merge so I'm not going to walk through the this algorithm I don't don't really like to show code but the basic idea is that we're going to sort them both first and then there's going to be this cursor that's going to walk through the the outer table and the inner table and sort of in lock step and they move down once they know that there isn't going to be a match anymore because the values are are inre or decreasing accordingly and in the case of the outer table we may have sorry the inner table we have to backtrack because we missed something because the outer table moved down and rep repea the value I'll show an example that in a second so again here's our same query when when you want to join R RNs so the join predicate is r r.
35:44 ID equals S ID so we're going to sort both relations on the ID column right so that's easy that's done and then now in the second phase when we do the probe uh or sorry the the merge we we have this cursor that starts at the beginning of both both relations and then we're going to compare across to see is the value from the outer table that my cursor is pointing at is that the same as the value that the inner table's cursor is pointing at and if yes we know we have a match if not then we we we move we move down
36:17 uh we move down based on uh what the values actually are so in the very beginning I say also too we we we're going to maintain some metadata on the on the in the table for this last value to say within the sort of last um sort of the last batch or range of values that I looked at what was that value in case I see that value again on the outer table then I need to backtrack there's some additional metadata say what's the offset to jump back into uh up that but for Simplicity we just assume that we are we are keeping track I'm just not showing it
36:49 here so in the very beginning the the the cursor on the outer table is pointing at idal 100 the cursor on the inner table is pointing ID 100 these are equivalent they're equal so I'll go ahead and mash the two tupal together and then that's in the output of my joint and then now the inner table's cursor is going to move move ahead by one we leave the outer outer table's cursor alone the inner table moves ahead by one and now I do the same check ID equal 100 ID equal 100 that's a match so I I produce an output tle uh accordingly
37:22 same thing now the cursor moves ahead on the inner table now I'm at 200 right and at this point here 100 doesn't equal 200 and 200 is greater than 100 so I know I need to iterate and move the outer table's cursor down by
37:39 one because I don't know what's going to come after this 100 uh and I don't know what uh and I know whatever it is it's has to be less than or equal to 200 if I could ever have a match on the inner
37:54 table so I go ahead and move move the move theable cursor down now we get 200 that's a match going to produce our output and now we move the inner inner cursor down by one we get two uh we get 400 now this point here now the value has changed on on the inner table so we go from we were at we were at 100 because that was the batch up above or the value up above now we go to this next one here now we said it to 200 because that's the last value that we saw before it
38:22 changed right and then now because 400 is greater than 200 uh I want to we don't a match there there is an ad joint here a joint tupal now we iterate the outer Tuple cursor down by one but now we see 200 again and at this point here we recognize oh the last value I saw before I changed on the inner table was 200 so I want to backtrack uh to where I was before the starting point for when I the last time I saw 200 because now there's there's a bunch of tupal that I didn't join with with with the the outer tables tupal so then now do same same thing 200 equal 200 that produces an output right so that's fine the inner table so inner
39:03 table's cursor moves down by one now at 400 do the same thing again the outer table's cursor is going to move down by one right because I've already moved down over here now we get to 300 300 is still less than 400 so I'm going to keep iterating this thing going down right because again I know that I saw 200 above I'm at 400 uh there isn't going to there isn't a 300 on this side so there's no reason to backtrack and this thing needs to keep moving for until it
39:28 till it hits 400 or greater than equal to 400 because I don't want to move the inner cursor down before the outer cursor moves all the way down yeah right so now we're at 400 400 equal 400 produce an output inner table moves down to 500 again we set our last value to 400 in case we ever see 400 on this side again right 400 is less than 500 so this is going to move down by one 500 equal 500 produce our output Tuple this thing moves down now we're at the end and we you just short circuit this well actually no take it back you need to keep scanning down on at least one more time here because you don't you don't know yet whether this is going to be 500
40:06 and therefore you needed the backtrack so again once I see 600 uh you can you can just stop you're done yes are these uh ID like when they're stor pages are they sted so means that wech like a page we mightet like all the way from 100 to or 400 your question is going back here uh that these are sorted like are these physically sorted on the uh like yes yes the question is are these physically sorted on the pages
40:38 yes right because this could be like again I I scan the table I scan table R scan table s then you do external merch external merch is going to write it out to a bunch of temp files uh in the order that they're that they're
40:52 sorted yeah I'm not showing page boundaries in this but you can imagine like if I need a backtrack I need to go back multile pages so that's that's why I didn't want to show the offset say because it's not just like oh just jump to the third offset this it's really jump to the the the offset that correspond or jump to the page that corresponds to the offset going so many so many values
41:11 back yes question if I already had a if the the data was already sorted do I sort again if it's sorted on joint ID no it's already sorted yeah but unclustered will not Ure that all the are sequ question the unclustered yet unclustered an unclustered index will not guarantee that the the data is sorted based on that index yes so your question is what sorry if you have a clustered index that like yeah it's sorted but locality is not uner right this ensures that
41:52 like oh you question like oh see what you're saying like the if you have a clustered index it could be within the slotted page it's still not sorted but they that's not an issue because you would go over the slot right so physically it might be stored different ways but the slot will be sorted by the value so the iterator is really going over the the cursor are going over the slot offsets and that that'll still be logically sorted correctly even though physically the bits may not
42:24 be okay so what's the cost of this thing well the Sorting the sort cost for R and S that's just what we talked about last class right that's assuming doing external merge sort and then the merge cost assuming you're not doing backtracking it's just read all the pages at M read all the pages n once and I'm
42:47 done and I don't again it's not a multi multiplicative for every single page on the outer table I got to go read every single page on the inner table as we saw in N Loop join I I only have to go fetch the outer and the inner tables
43:00 once right best case scenario is like every everything is all uh all the keys are unique and and they're all sorted and I want the backtrack right so if we go back to our example again right now with uh with with say 100 buffers to do our our sorting um the cost of sorting R is 4,000 the cost of sorting s is 2,000 adding them two together and then scanning them all at once the total cost is 7 7500
43:29 ios's much better than the the the the the naiveness loop join not as good as the index n Loop join because index n Loop join just does the Probe on on the index and super fast and we weren't we weren't including that the probe cost in our calculation
43:43 anyway so again we went from what 1.1 hours down to still uh you know 75 700 milliseconds that's pretty good so the worst case scenario of s merge join is if there's only one value uh in you know um there's only one value in in in in each column like all the IDS are
44:09 one right because I'm end up sorting it and not not produce anything different and then I'm just going fetching and doing backtrack over and over again right but in practice sometimes it is very useful especially if the query has an order by clause that just happens to be the same thing as your join Clause
44:30 because now again I kill two birds with one stone I I sort it to do my join and then the output of the data is of of the of the joint is sorted and then now I don't have to run my additional order by
44:42 clause or in the other way if the data is already sorted on disc as he was asking about then great then I don't I skip the first phase I skip the sword phase and just do the joint directly on
44:51 those all right doesn't always happen uh right but if if you can take advantage of that uh then it's a huge win right going back to the cost here right the the bulk of the cost here is from doing the sort phase right that's that's 6,000 ios's so if I can skip this and just do this then I'm basically at the index next Loop
45:17 joint right okay so the next algorith the last Al talk about is doing hash joint and the basic idea here is that we can exploit the fact that when similar to how when we were doing inserting to a hash table and then we do lookups on it well if if if if things have the same the keys have the same values then when I hash them they're going to end up the same location so the idea applies now when I want to do a join if I build my hash table on one table and then now I do lookups on on keys from in my join Clause into that table if the values are the same then I'm going to find a match
45:56 and then again that's that's equivalent of doing a look up on the B+ stream but what's going be different here is that we're going to build the hash table on what we'll call the outer table and then probe it with the inner table whereas like the next Loop join you would probe the index on on on the inner table but but a high level conception they're doing the same
46:15 thing so a simple joint house simple has joint algorithms have two phases in the build the build side of the build phase you scan through the the outer table you're going to have some hash function to build a hash table you can use whatever your favorite hash table implementation you want right cucko hashing linear prob hashing uh chain hashing lar probe is usually going be the fastest one because it's so simple
46:38 you build that hash table based on that join key and then now in the second phase you scan through the the the inner table and just probe that hashable to to find a match and if you do then you produce that as the
46:52 output so conceptually it just looks like this again it's two for Loops but now they're not nested because I'm going to Loop for every every T in the outer table build my hash table Loop for every single T in the inner table and uh and then prob the hash table and produce any
47:07 outputs right so again first phase I scan through R just hash it fill out this hash table that's going to sit it's just sitting in memory right it's not back back by the buffer pool because we don't want that because it's random IO so we want this to be in memory and then now I'm going to scan through S do the same thing do a probe and find any matches that we want
47:27 pretty simple right so one optimization we can do is something we actually talked about before I think when we talked about chain hashing we talked about you can put a you put a balloon filter in the in the bucket array so before I scan along the the chain which ends up being a sequential scan I check the balloom filter to see whether my key could even exist in the chain and then if it doesn't I know I don't keep going if it does then I do do I do check the the chain so I can essentially do the same thing now for my join so as I'm building
47:59 the the hash table on the build side the first phase for for the outer table uh I can also build a balloon filter and then now on the the probe side in the second phase as S as I'm scanning through S I first probe the the the filter see whether I have a match if I don't then I just ignore that you know drop that t if I do then I do go check the the hash table
48:27 right and the idea here is that the cost of going a doing a probe in the the the blend filter is is way less expensive cost way less than the cost of doing a probe in the hash table and so if my joint predicate or my my joint keys
48:42 are uh are unlikely to match then this is going to be a huge win for us like if I know that like I don't really have for for the adder table for the joint ID there isn't a lot of matching tupal in in the inner table then if I can throw as much as I can away with the the balloon fil in the beginning without touching the hash table then that's going to be super fast cuz the balloon f are usually going to sit in in CPU cache
49:03 yes sir is this um hashing only better if like the original key is long and we trying to use it like we are trying to trade from the with the computation of hash to like the actual uh actually comparing long composite Keys uh your question is uh when you say hashing hashing into the balloon filter or hashing into the hashing to the hash hash the question is is is Hash table only is Hash T hash join preferable uh when the join key is very long and therefore I don't have to do like a like a bitwise comparison of things yeah you still have to do that bitwise you bit by bit comparison bite by bite comparison
49:41 even if you match on the hash right so you point yes if I hash and I don't find a match like if the hash table is mostly empty then yeah that's G to be fast but if I have to start scanning down and because it's linear probing and start comparing keys I still have to do that key comparison I can't just check hashes because I could have collisions like two different Keys could hash the same thing so I always have to compare the full thing yeah so we basically trying to use
50:05 like the trade-off here is we compute hash for everything to like eliminate uh keys that doesn't have a hash collection because if the hash does not no so sa is uh that so so your question is like are we doing a hash dra because we can eliminate things when we when hashes don't have matches yeah understand why we have to pay the for instead of just trying to
50:30 compare all right so the question is why do you have to pay the cost to do a hash go let's go back here ignore the bloom filter okay so back here your question is why should I pay the cost on the probe side to Hash the key then do a look at the hash table and find find that my match versus just comparing the keys how do I find the keys though how do I find the keys on on the build on this
50:53 side right I have key key ID equals 1 2 34 right I have 1 2 34 over here 1 2 34 over there how how does how do how does how do I find it for that key over here how do I find it in this this is unsorted so I have to do a squential scan that's your nest Loop joint that sucks so this is basically an index for us that we're building on the fly so I can jump to
51:18 some offset or some location in my hash table that may not have exactly the two w that I want to do my match but it puts me in in ideally in the proximity of it so then when I start looking around to try to find it I'm looking for less
51:31 things yes just to clarify the biggest difference between this and the index version is that there we already have something built and here we're doing it just temporarily this question is is the difference between uh what we're describing here versus uh what I said before the index Loop join is it because this thing we're building on the Fly where index Loop join You're Building uh uh using an existing index
51:54 um at a high level yes but we'll see how we can we can take this further and handle spilling the disc uh whereas like in the index and loop join they don't they can't they can't do that very well there's optimization we'll see in a second but like the H hash table for joins if it's if it's an equality predicate is almost always going to be preferable to an index or a B plus
52:22 G right again it's there's no free lunch right we have to we have to find match is we either swal scan or we build a data structure to do it for us or use an existing one so here's how I'm showing you how to do this with the hash table
52:39 now okay again so this technique you're putting a blimp in front of it sometimes some systems call the sideway information passing right because the idea is that I'm passing information on this side of the join to my my sibling that's joining with me on the other side and you think of the relational model with these these tree data structures you so you're not really supposed to Route data from this guy up to the joint and back down to the other right but but it's it's an obvious technique you can do uh and it doesn't violate the relation model relational
53:09 albm okay so in the simple hash I showed you the hash table fits in memory that's easy right because it's not it's not it's not random iio we're not never go to disc we're just probing this hash table in memory and things are fine um but if it doesn't fit in memory
53:27 then we don't want our buffer pool manager to start swapping things out to dis uh because since the the hashing function sort of randomizes the the locality of data or the keys that we're trying to join on I'm proving to different locations to my hash table uh and at any time it could just be thrashing moving things back and forth
53:46 right so we we need a better approach again to avoid this random IO and try to maximize amount of sequential IO we can do and still do a hash join still use the hash table to speed things up
53:57 right so we're going to rely on that same Technique we saw at the end of last lecture where we broke up uh when we're doing the aggregations we broke up our table into into buckets have those spill to dis as needed but then when we do now the sort of the second phase of the algorithm we bring those buckets in one at a time so that they fit in memory and now since we we've sort of hashed and partitioned things at the first the first phase we know that the data that we need to join on has to be within the same sort of set of buckets at our level and not some R other
54:28 location so this is an old technique uh called called Partition hash join you'll sometimes see this referred to as the grace hash join um and then you know this is a classic technique from the 80s pretty much every system implements this of how to do hash joins when things don't fit into memory again the two phases are partitioning things up breaking up the buckets that that that that can spill a memory spill a dis and then we bring those buckets in incrementally and just do the joins based on those so the reason reason why it's called Grace hash join because it was uh it was invented by this group out of out of Japan who built this thing called a data machine called Grace and in one of the the like seminal papers out of this group was they talked about doing the grace hash
55:08 join uh so back in the 80s there was this big movement called for databased machines think of like you know Computing was so slow that uh everybody was trying to build these sort of specialized accelerators for databases and they called them database machines
55:22 um Grace wasn't the first one there's a lot of there was a lot of different versions of this so one of the first ones here this is from IDM I like I like this photo because it shows this guy in like a suit working on a on a database which is obviously how we work now uh but they would sell you special Hardware they do sorting in memory because sorting was so expensive so you know you buy this this Appliance
55:42 database system uh and it had the specialized Hardware to do this you know this one aspect of queries that was super expensive because again when you think about the the number of different operators that things you can support in a datab system it's not you don't need a general purpose CP you right because you're not going to be Bitcoin mining in your database system or doing some other random stuff right it's going to be you know a a regionally sized selection of of relational algebra operators so you can start specializing some of those the more expensive things uh and get get a huge win so in the 80s again people
56:13 since the 80s and 70s people been trying to do this and even now today there's a bunch of different companies that'll sell you different appliances right ter data will sell you something uh ex dat is probably the most famous one uh well Oracle sell you these these GI box units uh that again have like infin ban and specialized hardare to do things uh IBM had this thing called NAA was basically an fpga that did projections or sorry did scans or filtering directly on the hardware and repeated it through the
56:39 fpga there's another company also now in yellow brick uh from a few years ago they s an appliance that's basically their data warehouse running in a system uh but Terra dat and exod data are probably the most the most widely used ones like these things are expensive like each of these boxes is like5 million right and that's like and then you have to pay whatever multimillion multi-million dollar year uh support contract for them right the reason why this stuff usually doesn't pan out Le this stuff definitely in the 80s is because by the time it took you from like the to design whatever the specialized Hardware to to to then Fab it and then put it out for your customers Intel Motorola put out a new CPU and like because of mors you know mors law and all the benefits you got eventually uh you know got evaporated
57:22 but again people are still trying this is like the whole the gr database it's like specialized Hardware to make databas goas fter there's GPU databases there's uh people use fpas a lot to still today um but yeah like something better than than just a x86 CPU would be a huge one for databases okay so let's see how we do the partition hash drun so just like before when we talked about aggregations we're going to break up R and S into K buckets and so this just scanning through sequentially on on the outer table hashing it and writing it out into
57:54 a into the buckets but this is going to be you start to think of this as a like a a change hashtable we're just we just putting things into uh to to to so a list of values then I'll do the same thing on on the other side uh scan it and fill in in uh for the inner table and then now when I do the second phase I just go read the corresponding levels of the buckets from the outer table and the inner table and
58:24 then do my join and I could build another hash table in memory right like like when we s the simple hash table and you know on the outer and the inner and do the join that way or I could just honestly do a block Nest Loop join because everything's always going to be in memory and it's going to be really fast then now once I'm done the first level I go to the next level and I know there isn't going to be a tupal uh say on this side here on the inner table that's going to match to something on the outer table and in this other level because I've already hash it and make sure that it lands in in the right Bucket
58:53 Level and I scan through down and then I'm done right so what's one problem we could have well what if now as I'm hashing in the sort of first round and my uh and I've skewed my data skewed and a lot of the keys are ending up in the same bucket and now that that bucket doesn't fit in
59:16 memory right like the whole thing didn't fit in the first place but now when I purchase it again the bucket that bucket doesn't fit in memory well I just do this again do do another round recursively I've Take the bucket that didn't fit in memory hash it again using a different seed make more buckets and do the join once once everything spills the disc again the degener case the worst case scenario is there's like one join key that has a gajillion values and no matter if I hash it again it's still going to end up in uh you know it's all going to end up in the same Bucket Level
59:48 anyway uh so if you recognize this happens you just fall back to a block nested Loop join and and just do the joint just for that that one one step side keys that don't that has to spell a dis right and then yes the block and Nest Loop join sucks compares to compar to a uh you know compared to a hash join
1:00:08 but by avoiding random IO right you know yes it's going to be slightly slower but it's still it's going be almost always sequential IO at this point here and this is Gen this is like the extreme case of like I have one person that has say that you have an account and orders there's one person has a million orders or a billion orders for for whatever reason and it doesn't fit in
1:00:31 memory all right so let's see how to we reur the partitioning so again same thing the first phase I hash all everything on the outer table using the same hash function with the first seed but let's say this this key here whatever key is landing in this in this bucket here level one and that's get getting completely full so then now in the second phase I just pass through the other buckets that didn't get full like zero and K minus one is get passed over to the next round don't have to copy anything you just say just gets moved over but then I use a different C for the hash function again and I go do a second pass over this data hash it up split up to to smaller buckets like
1:01:08 that and then now things have evenly spread out now things can fit in memory so then now on the probe side you have there some additional metadata got to keep track of if I Hash a key and it lands in either the first or the last bucket I know that wasn't recursively partitioned so I know I can just jump to the right you know the right bucket offset and that has the data that I want but if I Hash a value now that goes into the bucket that ially partitioned then I know I need to do another round of of hashing to go find the exact location that has the data that I
1:01:41 want right so what's the cost of a uh uh doing hash join well if I don't need to do recursive partitioning then it's going to be 3 * m plus n right because in the partition phase I got to read all of the uh both the outer table and the inner table once write it out once hence the the 2 M plus n but then now uh in the second phase I can read read them all back in every page once
1:02:15 and it's n plus n yes so we hash the inner table how do we know which blocks have to go through recursive hash and which do not this question is if if I hash if I hash the inner table how do I know in this in this case here how do I know that if I Hash a bucket one I I should go partitioning so you just pass the metadata over to say you say here's the here's the buckets in the first round of the hashing that got split therefore you do another round like I can recursively partition this infinitely you wouldn't want to do that in practice one is usually one one additional round would be would be enough um but just it's easy metadata
1:02:57 all right so again going back to our example four uh the cost analysis be 3 * n plus n so I got to read a um to 100 ios's for the outer table 50 iOS for the inner table sorry 1 th000 iOS for the in outer table 500 for the inner table add them two together multiply that by three uh and you get 0.45
1:03:20 seconds so better than than sort mer Jo sort mer join was what 75 7500 iOS again obviously there's gener of cases where this this won't work but the the external merge or the merge algorith s measure joint algorith would have the same problems if one key has all the values all the
1:03:39 matches so there's one additional oposition we can do uh called a what's called a hybrid hash join and so this is idea has been floating around for a while as far as I know nobody actually implements this because it's really hard to get this correct uh because you have to know something about the data ahead of time that you may not be able to know and the idea here is that if you recognize that there's some key that's going to be super hot meaning I'm going to have to on the on the on the the the inner table is going to do a bunch of probes and hit this key over and over
1:04:14 again then rather than just spilling it to disk in the first phase SP like spilling all the buckets to the to disc in the first phase I'll just keep one bucket or one one one a small subset at a level that I know are hot keep those in memory let everything else spill a dis and then now I don't have to worry about reading that back in over and over again right or writing out the F in the first case so say for whatever reason there's some key they're all hashing to this first bucket here so I what I'll say then is okay well this level here this is going to reside in memory and I don't go through that second phase I just do the join as as as it happens as I'm doing the probe and then everything else that'll spill a disc and I'll do the second phase a bring it back in
1:04:56 memory one one bucket level at a time and then you do the joint on that again the reason why this is hard because you you you kind of want to know what's going to be the hot key ahead of time but you may not have any metadata for that right most Data Systems will keep track of the Heavy Hitters like what's the most common key uh but that's just you know that's just just within one table what maybe the hottest key in this uh in this table may not be the hot key you're going to join on in this table so you basically have to take statistics from two different things and try to try to combine them together which is not easy to
1:05:32 do because you have an incomplete view of the two tables all right so hash tables can be of any sorry the inner table can be any of size uh but ideally if I get my outer table to fit entirely in memory that's fantastic because then then I don't have to spill things at DIS um if I know the exact size of the outer table ahead of time then we can use a a static size hash table uh that is sort of almost perfectly uh how is it it's exactly the size that you need things hash to exact location and then there's less overhead to do the join but typical typically you don't have
1:06:10 this so what'll happen is like you're in like in most you say from when I run a query I'm I allow the query to allocate this amount much of memory for my hash tables and I hope I get that right and then if I get wrong and I have to resize it then to do the thing where you lock the whole thing and double the size and and load it back up but that's going to be super slow and we want to avoid
1:06:34 that all right so here's the summary of all joint AGS that we talked about here today uh and roughly with their IO cost and again the in general the hash join for really large data sets is almost always going to be
1:06:47 preferable uh even though it seems kind of crazy like I I'm building this data structure on the Fly and then immediately throwing it away after I run the query well yes but that's going to be better than uh than doing bun of random ios's or doing doing squential iOS over and over again I pay the Cal IO cost to build the hash table once and then if I'm if I need to spild a disc I can handle that but then now I don't have to do a bunch of random iOS to to do the
1:07:14 joins because I sort of reduce the locality of where data could actually exist okay yesable because you don't know the value question is why is inex Jo variable because you don't know what the value of the C is could be a B plus tree could be a try it could be a hash
1:07:40 table right so you said if it's log it's a B+ you could you could put a log n there well it's also variable too because it's it's um like if if I have have a one to many join meaning like for one key on the outer table I have multiple Keys that'll match it on the inner table and I might Pro my index and then scan along a bunch bunch of leaf nodes to get all the matches for that so you don't know what that's going to be at least at this point when we're talking about this because depends on the data depends on the the the schema depends on the query
1:08:16 so even though it's still an equality predicate it's like for one key give me multiple uh one key in the outer table give me multiple keys on on the inner table so it's variable whereas like in a block Nest Loop joint you basically scan the whole thing I mean you can be clever in some cases like if you know if you know it's one to one uh which is not always the case then like when I'm doing my block n Loop join
1:08:38 if I if I say I know there has to be exactly one and only one match on the inner table soon as I find it then I can break out of the the inner loop right but youd have to know
1:08:50 that yes how accurate do these numbers actually end up being after you take into account like CPU cost it's question how accurate these numbers actually be when you take account of CPU cost um these numbers are are okay right the where you have problems are are how are you going to like these formulas are okay right um
1:09:14 it's it's these ones are going to be the problem the M plus n because let's say again say I'm doing a a three table joint in my query how do I how can I predict I'm going to have trouble predicting what's the number two going to come out of the first join then feed into the second join so that means my M or M is going and m m or M is going to be off that's just for two joints what if I have thousand joins which some queries actually do they're not you know they're not they're not super common but they do exist but now you're basically building like crappy statistics off crappy statistics off crappy statistics
1:09:46 and the numbers get way off yeah and then we'll see this again after the midterm but this the one thing is that all all the DAT systems are going to uh underestimate how many tbos are going to come out from a from a joint operator
1:10:02 because they're going to make a bunch of assumptions about predicates like like they're going to be non-correlated even though they will be correlated so the the the calcul the estimates get way way off yes just to clarify about the sort one it has to be not just sorted but also like clustered right so if if we're just using a b Tree on the main index of of of a table it's still sorted but there's going to be a lot of thrashing
1:10:24 going through in assorted order because the question is uh for the inex loop join uh that it's not enough to say that the I was talking about s mer join yeah your concerns about things thrashing for the Sorting or what in the sorted merge join you said that if we already have something sorted we don't have to resort right yes but like the index of the table is already sorted but we can't use that so so so
1:10:50 so data can be stored without an index right so like when we talk about these parket files we like there's these open source file formats like I could have my front end application make me a bunch of files from the from the front end database and then it becomes basically immutable but I can sort them as I store it and then I don't have an index for how it's sorted just I did external M sort and and wrote it out so you so it doesn't always have to have an index to be sorted so then your other point was if you did have an index though is it the case that the the
1:11:21 could you still have thrashing because now as you're uh because you're doing random probes into the index well no because if it's clustered on the if the data is clustered you don't need to the probe the index you just walk through you need an iterator or your cursor to be able to walk through the pages in in sort of order but you don't need to refer to the index for
1:11:43 that yeah like if things are sorted ahead of time it lates a bunch of these things but most data is it's not going to be sorted and again like a b plus3 will be log n a hash table could be 01 and so you're you know the probe doing du to hashing is still potentially much faster than doing a probe into a B+
1:12:07 tree so then you say okay what if I have a hash table and I want to do an inex andx Loop join is that the equivalent as basically hash join sort of yes but the uh again you you lose the flexibility of being able to do that recursive partitioning we talked about
1:12:27 before so I don't think I I we we can go check but I I think if you have a hash index uh and you do a join post won't try to pick it up to do next Loop join but I'm not sure about
1:12:40 that okay all right so hashing is as I said is always going to be better than the than sorting uh and basically as I said before there may be cases where things already sorted ahead of time or uh you need the results to be sorted this the sort mer joint algorthm actually might be better but again the the good Data Systems that that can support these different operators they'll make the decision on the Fly for you which one actually you should be
1:13:05 using okay all right next class new ter exam not that bad this databases right it's good stuff uh okay yeah next class midterm exam uh any questions email me or post on Piaza and then I said I have I have additional office hours tomorrow at 1 p.m. in my office uh if you want to sort of check anything at right before the exam okay I need something refreshing when I get finished manifesting too cold a whole B like Smith and Wesson one court and my thoughts hip hop related write a rhyme in my P intoxicated lyrics are quicker with a simple Mo lier since I'm mer City Slicker play waves are pick up rhes I create rotate at a r too quick to duplicate feel a breeze as a skate at fhe when I hold it real tight then I'm in flight then we ignite but starts to boil you I heat up the party for you let my girl R me my mic down with oil Rec still turn with third de burn for one man I heat up your brain give it a sun
1:14:11 so just cool let the temperature rise to cool it all with s eyes [Music]