CMU Database Group · 1:17:56 · https://www.youtube.com/watch?v=mM3sFwSuGNY
1. <Untitled Chapter 1>
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 so uh today we're going to be start talking about how start executing queries and running operations on on the data that that are coming up from from the scans they're doing down below again reminder everything for you guys homework 3 is due this Sunday coming up the plan is to have it due this Sunday and then give you out the solutions and gred responses by the following Monday because you'll need it for the exam on
0:49 next Wednesday um project two again we do after uh after fall break in the 27 and as I posted last night in Pata there's now a online study guide with the practice exam you can use with the solutions and explanations uh and then there's the study guide tells you basically what you need to do the main thing you need to show up is with your CMU ID so we know who is who when you fill it out okay any questions about any of these
1:14 things again homework 3 is do the Sunday we'll get you get out the the answers by by Monday morning okay so so as I said uh last time like now that we've discussed like how to actually build indexes and how to actually uh organize organize a data on the disk and we're now going up the stack further and we can talk about how do we take all those components we've built so far and and run queries on them
1:41 so for the next four lectures we're going to talk basically the low-level operator algorithms we need need to to execute you know full more more complicated queries uh how we actually want to organize the system to to to process those those queries and process meaning how do we move data between the the different operators in our query plan and then we'll a little bit about the runtime architecture for how you actually build a system make whether you make it multi-threaded multi-process and so forth again we're focusing on single node systems today or for for this part of the lecture but we'll see how we can extend all these things to do distribut execution uh later in the semester okay
2:16 and again for this today's lecture this will be on the on the on the um on the midterm Monday's class and going forward will not be on the midterm sorry keep hit the wrong button all right so we saw this diagram earlier in semester uh of of a query plan right I said roughly that you take the SQL query you run into some parser it generates Absa sja tree and then from the abry you you can then generate a query plan we haven't talked exactly what the query plan looks like and what these operators actually look like just yet but at a high level you can think of it as a tree often times most times it's going to be a tree uh it's better to be a dag but most systems don't do that and the idea is that in the the leaf nodes of the tree is where we're going to be reading data from from from some Source
3:01 like from a table from a file you know some lower part of the system and data is going to move up from one operator to the next right so in this case here we're scanning R we feed this up into a joint operator we do a joint on S we feed this up to projection and then the top the root node where the projection is that's the final output that we're sending back to the to the client right to to the response for this query and so this is obviously a PowerPoint diagram it doesn't say anything about what these blocks of data that I'm moving around are right what the granularity is how often we're doing it uh is the bottom pushing it up are we pulling it up right there's a bunch of those things we'll discuss after fall break but a high L this is the general idea that data is Flowing from one operator to the next uh in order to compute some portion of the query and then the root or the top of the tree is what the client gets as the final output
3:54 right so since we've been talking all the semester about discording systems right the same assumption we had before that when we want to do something on a piece of data or a table or some collection of data that we can't assume that everything's going to fit in main memory we're going to have the same issue when we actually start running these operators that implement the the the nodes in the query plan uh where we can't assume that the intermediate
4:17 results of of these operators fit entirely in Dam or fit entirely in memory right going back here what if it's the case that like I only have a gig a g gig of memory but are it's feeding up to this hashable this hash table ends up being two gigs in size well I need to be able to accommodate that and have have my hashtable spill a dis because again I want to have the illusion that I have more memory than I actually
4:40 do so in the same way that we built the buffer pool manager to manage the you know the the bring pages in as we're doing scans and so forth we're going to use the buffal manager again the same thing you built for project one to spill intermediate results to like temp data on disk right and because of this because
5:00 we we could be end up going to dis if necessary that means that our implementation is typically going to prefer algorithms again that are that are going to maximize the amount of SW IO uh and minimize the amount of random
5:13 IO because again doing random disse is more expensive than reading much you stride of data that all contiguous with each other right so again we don't want the OS to manage the memory for us we're going to do it ourselves and there and because we know that we're the ones managing memory we'll choose algorithms that can maximize this sequential
5:33 iio so one of the the the backbones of the fundamental algorithm we're going to use for a lot of these different operators is sorting all right recall that when we talked about the relational model at the very beginning of the semester we said that the it's inherently unsorted right it's based on set algebra right it's an unordered set unordered collection of data uh without any duplicates in relational systems and the actual implementation of these systems can be bag algebra where it is still unordered
6:01 but there can be duplicates and so we'll have to see how we can use sorting to to to remove the unnecessary duplicates as needed so obviously there be some applications that are going to want data to be sorted like if there's a nice order by clause in our select statement
6:18 then we need to be able to sort our data to handle that but other times also too even though that the the query is not asking for our data to be explicitly sorted through an order by Clause some of these algorithms we going to use like for aggregations and joins we'll see next class will actually be faster if we sort things ahead of time then do whatever is the operation that we want to do but this seems kind of crazy that I want to do a bunch of uh extra work to sort this
6:43 thing uh knowing that I may still spill dis but then when I actually do whatever the processing I need for that given operator because it's sorted that's going to make my life a lot easier so it's worth to pay that upfront cost to get the benefits later on in some cases uh in some systems like in SQL server for example uh I mean we'll see how to do sorting with external Mur sort like in SQL Server it can say hey this data would be great if it was sorted and if I had an index so it'll build you a B+ tree they called a spooling index they'll build a B+ tree just for your query do whatever it is the operator wants to do to process the data and then immediately throw it
7:18 away right again it seems crazy but again the the the construction cost of that of that data structure or the construction cost of sorting the data ahead of time will Max maximize the amount of sequential IO we have later on and that's going to make our life a lot
7:34 easier right so as again as I said we need to account for the fact that we may have to spill a disc if everything can fit in memory well that's easy right pick whatever your favorite sorting Al you learned in in you know like early CS classes right merge sort quick sort Tim sort uh gnome sort cocktail shaker Shaker sort if you look at the Wikipedia there's a bunch of them
8:00 uh in general quick swort and Tim sort are probably the best the best two that you want so if everything's in memory our life is easy we just use whatever you learned in again in early CS classes to sort things it's when you have to spill a des that's the challenge that that we're trying to overcome today
8:16 right that we need to account for that we may have to read the data in and we can't bring it all of it in and how can we divide up the problem so that we can still get a globally sorted data that doesn't fit entirely in main memory
8:29 so most datab systems are going to use quick sort uh or uh variations of this or insertion sort sometimes or everything fits in memory like post will use quick sort and if you look at the query plan it'll tell you that it's using quick sort right because if it fits everything in memory and then obviously if you're you know how would you know that you can use quick sort versus a external M sort or the dis Bas sorting well you make you make an estimation about how much data you think you're going to need coming up the query plan right coming up between the different operators and decide oh well the data is this size I have this amount of memory in my my buffer pool to sort it therefore I can use quick sort and if you get it wrong then you can just stop
9:06 and and revert back to uh to use to use uh you know a dis based sorting Pro can't do that other systems can if you recognize you get it wrong you adapt your query plan and change it right but we we we'll ignore that for now all right so today we're going to talk again about the two basic sorting algorithms that we going to care about the most in in in a in a dis disc database system
9:28 top end s topend Heap swort is a special case when when you know what the query actually is want once and therefore you don't have to do sort you don't have to sort everything and external merge sort would be the core algorithm we use to do dis Bas sorting and then we'll see then how we can use that sort of data to then do aggregations and then also compare it against hashing which will then segue us into how to je joins next class and then we'll finish up with a guest lecture guess less talk from uh DBT which is a very interesting Tool uh you may have never heard of it but it's widely used everywhere pretty much every single company in the world is using DBT um and the reason why you may have heard of it because you don't have you guys are students you don't need data when you start getting data at your startup or your company whatever it is then you realize what you need DBT for but uh Drew will give a talk and and explain
10:18 why okay so as I said top end Heap Sort is a special case where if you have a query with an order by Clause with a limit then you know that the D know that it doesn't need to globally sort everything it just needs to get whatever the subset is for the the the greatest of the smallest values based on what the order by Clause is so in this case here my query is getting all the student IDs
10:43 or getting all the the the student records from the roll table ordering them based on the student ID in ascending order uh but then now we're adding this fetch first four rows with ties Clause we didn't talk about limits but this basically says order by the student ID but give me the first four values uh like the top values for that sort uh sorting and then with ti specifies whether you want to include the the records with ties or
11:07 not so the way you would do this is that assume you have this original data and for Simplicity Reasons I'm showing as as a single column like this all continuous data but you basically allocate a sort of Heap data structure like a priority queue or something something pretty simple um and the idea is that as you scan along the original data you just insert into the sort of heap if you have a free space or if there isn't meaning like they're all occupied then you check to see whether the value that you're looking at is greater than the the highest value in my sorted heap if yes in this case because I want things in ascending order then I know I just ignore it right so in this case here the first thing we land on is three our sort of Heap is empty so we put in the front
11:49 then we land on four we have an extra spot we put it after three like that six goes there two goes two is less than three so we just slide everybody over and then now we can fill in two
11:59 and now we come across N 9 is greater than six so we know that because they're only asking for the four top values this query never need to look at nine so we just ignore it and skip it and keep going then we get to one in this case here our s of Heap is full so we just slide everybody over drop Six make a free space for one insert one now we see four now we already have a four in there so we we have to recognize that but again they they're asking for ties so we just add a little bit more more memory to the end of this to start putting in additional things and obviously we have to keep track of like are we going past the original four because we have ties
12:36 or are we you know are we and not just adding things we think we have more space so keeping scanning down Cas case four we add it again we find the eight we know we don't need it we skip it and we're
12:50 done right the advantage of this approach is that it's one pass over the data and I didn't actually have to sort anything right I had my little My My Little sorted buffer uh Heap on the side and I just used that to fill in the data that I need I didn't have to do the quick sort pivots or anything like that it was one pass over the data and this would be super fast um well if your data is pedabytes and you you know that that's G be a problem but
13:17 like uh you know having doing one pass over an algorith over data is always gonna be a huge win so most most of the high-end systems do this postest do does this I don't know whether my does and I think dctb can do do this as well right because this is such a clear win and this like give me the top 10 elements based on some ranking is is is a pretty common thing right think of like a leaderboard
13:42 like in this class or like any kind of online game giving the top 10 players that's going to run this algorithm okay so also in this case too like because I'm doing one pass the original data I just have you know I can have one buffer pull frame just use that to fetch in something scan it throw it away and get get the next thing I can do pre fetching other op other optimization tricks we talked about before but like I really only need one buffer for the data I'm reading and then another buffer or so for my my
14:13 Heap all right so what if we have to do a more General s sorting and again everything doesn't fit in disk uh then we're going to rely on what is called external merge sort and again most databas systems are are going to be able to support this because otherwise if you try to sort data that and you can't spill a dis you're going to run out of memory or if you start using quick sort
14:34 uh it's going to be really really slow because that's going to be a bunch of random iio so external merge sort is going to be a divide and conquer approach where we're going to split up the data that we need to sort into smaller units called runs and the idea is that we're going to sort Those runs by in memory and then write them out the dis to make room for the next things we need to sort and then we're going to do this through multiple rounds or multip multiple passes
14:59 until we end up with a globally sorted uh complete complete data set so what's going to be confusing is that what I'm describing today is the external merge sort algorithm we're also going to use this algorithm next class when we talk about the merge sort so in your merge sort algorithm for the sort phase you can use external merge sort uh which has its own separate sorting emerging phases so for now we we can ignore that but next class I'll try to be very careful say like what's the external merge sort versus what's the the sort
15:25 merge um all right so again the first pass we're going to get sort chunks of data that fit into memory and then rent them sorted chunks back out the disk and then the second pass we'll read those sort of runs back in uh and then just merge them together and produce more larger runs write those back out and keep doing this until we've sorted
15:44 everything all right so let's see what oh actually before we get to that let's let's first talk about what what are we actually going to restore uh in these buffers or these Pages as as we sorting so you can sort of think of what we need to sort is is a combination of key value pairs
15:59 right the key is going to be whatever whatever's in the order by clause or whatever it is that we're asking being asked to sort and then the value could either be the the Tuple the record that we actually need to sort or the record
16:14 ID right so again and the way to think about this is when you actually want to materialize the final result that you need to give back to uh to the client or the application that ex the query and so the way think about this is is notion between early materialization and late materialization
16:29 in early materialization the idea is that as I'm sorting the data I have the full to full tle that corresponds to the key that I'm actually sorting on so that I don't have to go back on up as I go up the further query plan I don't have to go back to the original data and get the rest of the tubal in the case of light materialization you just have a record ID right and what happens there is I can do all the Sorting I need just based on the keys because that's all the information I need but then later on in the query plan if I had to do anything else that needs the rest of the tupal I have to go then fetch that from
17:06 dis right so say like if I have a billion tupes uh and I have a filter where I remove 99% of them and then only then I sort it and then I go I need to go back and get the rest of the data in that case uh late materialization is going to be a big win because I threw I didn't have to copy a bunch of data around that I didn't end up actually needing which is going to be one of the ultimate goals we have you know when we try optimize queries but in the case of
17:32 uh if if I didn't filter out all those 99% of the tupes then after I do my sorting uh or after I do my my filter and then my sorting then I got to go back and fetch all that data again which might be more much more you know so I basically have to read the data twice so that would suck um so there's not and you know depending on the workload depending on the data depending on the query one of these approaches might be better than another if you're building a row store system you typically typically do early materialization because you go back to the page and all the data you need is right there in the column Source system some of them will actually try to do late materialization but in some cases you you don't actually want to do this we'll cover this more when we when we um we talk about query execution I just be mindful that like I'm going to show these algorithms in terms of just like here's the key and we're done but actually it's the key plus the value and that value could be actually quite large
18:23 yes so what happens if we sort by like two keys one is like the primary and like the primary the same we store by the secondary key do we use the early materialization but have two keys or uh but just because oh sorry do we use the early materialization because we can just look for primary secondary key within thatle or do we use lit materialization but keep two keys yeah the question is if I'm yeah so you're doing sorting based on the primary key
18:50 like uh primary first then secondary like an order by Clause has two has two okay and the question is do I do you do what sorry so do do both early materialization oration work for like multiple keys I know early materialization for sure work because you can just look up the other keys in the two hole but for late materialization do we multiple keys right so question is say Let's ignore actually the indexes because the answer is the same right question is like if I'm sorting based on two keys and say the first key is the primary key um
19:26 could you use an if you have a B plus tree could you just do that sorting on the primary key and then do additional sorting based on the the additional key afterwards uh depends on whether the data is actually sorted a cluster based on that primary key we'll see later on typically though you want to get you need to get both of the keys and try to do the Sorting all together so you would sort of materialize the key you want to sort on and then look at that and whether or not you go get the rest of the Tule depends on when you're doing these two different
19:52 approaches I don't know if any system can do I think what you originally proposed like you're using two different indexes to sort at the same time I don't think you can do that okay so let's use a uh let's sort of a simplified example of the external M we'll do what is called a two-way two-way external mer sort and then in this case the number two corresponds to the the number of runs I'm going to bring into memory and merge together to produce a new sorted run right so if you did like a three-way merge sort you could bring in uh you bring three pages and merge them together
20:30 yes yes this question is with late materialization do I only bring the keys in to memory and sort them I mean yes but my just the key value pairs like the key and the record ID even that might be really huge and I have to spill a dis the idea is that I'm not copying around the the the rest of the tupal data as I'm you know putting things in sort of run and so
21:01 forth again think of like when you implemented quick sort in like you know CS 101 you just given a bunch of numbers and you have you know sort them but it's actually you know it's a it's a key value pair it's like there's a payload you have to actually copy around as well so when you start doing the the the pivots and moving things around you got to copy that payload as
21:19 well okay all right so we're going to do two way external M sort uh we're going to assume in this case here the data is be broken on pages and then now we have to specify that we how many buffer uh pool Pages or frames we're going to be allowed to use to do our sorting right because we can't assume we have infinite amount of memory we have to be told how much memory we're allowed to use and for Simplicity you know we can assume that in this example here we just you know we have you know we use three pages right uh three three three buffal pages the most simplistic one but in a real system you obviously want to use as much memory as you can to do the Sorting cu then you it' be fewer passes going back back and forth at disk but if you're running other queries at the same time you don't want the one query that's doing sorting to slow down and and trash your buffer pool for everyone else so typically there's a knob or a parameter you can set to say how much memory you're allowed to use for for sorting
22:15 for any particular query you can change it on a per query basis but usually there's a global valuable Global value you set all right so in the first pass pass zero all we're going to do is is just read one page of of from the table in memory at a time sort it uh to create this new run and just write that back out to dis right and we'll repeat this for every single page in our table until they're all all
22:43 sorted then in the subsequent passes uh we're going to recursively merge those those pairs of runs that are contigous to each other uh bring them in sort of have a cursor iterate through them compare values and this right out to a new output buffer uh the sort of the values in that sort of order and we do this for all the sort of runs we have and once we're done then we go back and repeat the process over and over again until we end up with a single
23:08 run that has all the data sorted yes can beell tur because like Zer seems kind of independent with each other yes her statement and she's correct can this be done in parallel because pass zero is independent yes but for for Simplicity I'm not even really talking about workers or threads here but yes you
23:26 could yes allate a new dis page toore the s yes so his question is he's correct do you need to allocate a new dis page to sort the sort of run yes you would have like a temp page that's that still be backed by the buffer pool but like it's like a scratch base but then I can deallocate it once I know I'm not going to need that run anymore right so like if you're stupid about it you you would need three copy you you need uh
23:54 three times the number of pages of the original table size because I would have you know you know the the sorted page and the new output page and the original data right but you can throw away Pages you throw away runs from Pages Pages for runs once you once you merge them that typically won't cause the storage problem it you it typically won't call a storage cause a storage problem yeah like like what do you mean what do you mean by storage problem I need to large
24:18 table size table question if I need to start a really large table do I need double size the disc yes but this like what's the alternative right you try to sort in place that be be super slow right disc is cheap now right and serious like it's
24:39 uh you know it's it may not be fast right mvme is getting much much faster but like it's I forget what the price per gigabyte is it's nothing right inste if you go to S3 it's nothing at least to get it once all right so let's walk through an example so uh again we're doing two-way two-way external M sort so at the very beginning we just have our original data and assume here I'm just drawing uh in each each page there's two values right or two keys and I'm not showing what what the values are whether it's record ID or or the actual tupal data again for this visualization it doesn't matter so again and in past zero we're just going to scan through read every page in and then just sort the two keys that are inside that
25:21 page right so then at the beginning of page one I have now uh a a runs of size size one of one page so now what I'm going to do is uh in in to produce the output of the second the next pass I'm going to take two contigous pages again locally each page is sorted within the keys that they have but across the two pages themselves they're not they're not globally sorted so I'm going to take these two guys here
25:51 and I'll allocate one output buffer for me to write data into right so I have to bring these two two two pages in I have an out put buffer to write some data out right and then now you just have a cursor that's just going to scan through them sequentially and just whatever the cursor is looking at the first page and whatever the cursor is looking at the other page compare them whatever one whatever one is less that get gets written out and then the one that I put in there that cursor moves moves ahead by one now I do the same thing compare
26:19 the two values or two keys that the cursor are pointing to write out whatever one is the smallest iterate that cursor and now that my my this page here the two and the six that's full I write that out the disc Al you know reuse the memory now to for new output buffer to continue the rest of the the the merging of the two
26:40 runs so again I only need in this example here I only needed three pages two for the input one for the output so I can just now then just go do that one by one for all the other ones in the case of the last the last uh page over here it didn't have two two pages it only had one uh so I could be smart and say I don't have to bring that in just to write it back out I could say oh this thing is already locally sorted I don't need to merge with anything else
27:05 just carried over to the next next phase next pass and then now I'll do the same thing the next pass right I'll bring in from the sort of the first set over here I'll bring in the first page 2 three and the second page 47 have my cursor uh scan through look at them compare values and write them out to uh to to the output new output pages
27:29 and then now within that run of size four there the the data is locally sorted and I keep recursively doing this until I end up at the bottom with now a Lo a a globally sorted uh globally sorted data
27:43 set yes this question are these all in memory um no so going going back here so at this point here I only have uh do my poter pointer and you can't see it I have the page where it says 34 where the arrow is pointing to and I have the page where 2 six is and that's pointing to and then I have this output page everything else is out on disk right so then now once this thing gets full right at this point here then I write out the two three page reuse the memory now for this next one to fill in 4 six and then when that's done I do that again that incrementally for all all the other uh
28:23 uh run pairs until I produce uh run of size two so the number of passes here is going to be uh 1 plus log 2N the plus one is that first pass zero where I have to again make my small little uh you know small runs of size one and the log 2 N is almost like again like the uh you know it's like traversing the B plus tree where I'm cutting down by half the number of things I have to look at or number of passes I need as you go
28:54 down so the total IO cost of of sorting this data is two 2 N where n is the number of keys I need to sort um and then times the number of passes as I go down so this obviously would would suck to have like you know log 2N again typically in algorithm class that sounds great log you know log two B you know log 2 N that's great but then think of like I have a billion
29:25 pages right that log 2N is is not going to be that great so the way to make this even better is we want to change this two to a larger value because that means we can we can bring in more more more pages into memory at a time and have larger sort of runs so we don't have to go through so so many
29:42 passes right so again in my example here the number of buffer pull Pages we need is three because it's you know two for the inputs one for the output but if we have more space available then you know we we can try to do more things that you bring more things in at the same time
29:58 but if we just do the naive example where I showed before where we just sequentially or with a single worker thread go look at sort of one run at a time then it's not going to be that fast so we there are some tricks to optimize that we'll see in a second so in general the the the for a sort of General mway sorting algorithm it's going to be have B buffer pools and we take the ceiling of n divided by B again that's because we could have Pages at the end that don't uh don't easily or equally fill up uh all the possible runs we could have within that last SE
30:33 section and then in the subsequent passes we just need to bring in uh B minus one pages into memory because we always need one one page as output right and then it's plug and chug on the total number of passes to get the total IO cost for this as
30:51 well it's pretty clever right like this is uh this divide and conquer approach is widely used in databases in other systems because it's breaking the problem out to smaller chunks and then making so that each each sort of chunk of the problem is is manageable
31:05 yes let's say we have like two outut pages in that like when the first one get full you can send it to dis and you can use the second one to yes so he's saying what if you had two output Pages couldn't you then basically inter leave IO it's called double buffering two more slides yes is this faster than just doing a two-way merge in parallel because you can still use all the buffer pool pages that way this question is is this still faster than doing a 2-a merge in parallel uh
31:35 because you can still use all the buffer pool um I so your question is like should I still have like could I have multiple threads doing two-way at the same time um the challenge with that one is going to be if you have well in the old days you would not want to do that because you couldn't have so many parallel requests to the disc nowadays the disc cues are actually quite large so you could eventually do that but in general ends up being the
32:07 same actually no in that case you would end up WR you still have to if you're if you do what you're proposing you're you're still going to have a large number of passes you may be reading and writing it out over and over again for I use a bunch of memory I use all my memory to sort things I'm it's fewer passes like the tree gets shrunk so that that I think that's going to be always better to do even even if you have parallel
32:30 iio yes using the last page the merg result yes so but the merg result will for sure be bigger than the runs so what if we run like one p is not good enough holding the merge of the output that's fine right again going back here when I was here again I have my output page I'm putting two I put in three it's full write that out and just read use the memory and then for the for the next one right because again like as I'm doing the merge I don't have to go back and look at the page at the output page I just
33:09 wrote so that's why I can I can write it out and reuse the memory okay so look how the math works out going through this example here so say that we want to sort some data uh and we have 108 pages with five rable pages so n equal 108 b equal 5 so in pass Zer again we take the ceiling of End by five because we're going to break it up into uh to to sort of runs of five pages each so we up about 22
33:37 right and the last run has a remainder it's only it's only it's only three pages then in the subsequent pass again now we're going to be sorting together putting together pages of of of five pages so since we have four pages we can bring to memory we're going to end producing output runs of size 20 pages right so we're multiplying the the size of the sort of run is multiply four as we're going down then the subsequent pass we end up with uh getting down to to 80 pages with with uh with only two sort of runs then in the final pass we end up with the the completed sort of run of 180
34:14 pages and then the the formula works out like this so in this case here we it only took four passes again 108 pages is nothing think if you have you know a a billion records paby of data this you know this algorithm is still going to work in that
34:32 case so the exact details of like you know uh you can you do asynchronous IO to write things out in the background while you're reading other things all that's going to depend on the hardware all that's going to depend on what what the system actually implements right how much memory you should use allocate for a query depends on what else is running in the system so it's not like these values there's not like like there's not going give you values for n and B that would be optimal for any possible situation right the answer it always depends on databases
34:59 so now the optimization that he brought up and he's correct is that the the problem with this with the sort of general algor that I showed is is you basically have this phase where you're reading things in or writing things out
35:10 right and as we talked about before dis wres are going to be slow right worst case scenario you know tens of milliseconds if you're going to S3 hundreds of milliseconds um but even then your CPU is blocked waiting for the the next batch of things you have to go read in
35:28 so a better a better approach is to basically divide your memory into half where you have half the buffers being used to sort some data you have in memory right now and then the other half is being used to fetch the next things
35:40 uh that I'm going to need and you're basically alternating back and forth of what of you know what sort of phase is writing writing things out or what which of the sets of buffers are writing data out right so this will be nice because you reduce the the time you have to wait for Io because the system is always going to be able to have something to do some some work to be done because data will be in
36:00 memory so you can think of like really simple say this's our buffer pool and we have basically three pages and we have one page for the output buffer so if we do the basic algor I showed before we bring the first set of pages in sort them into our output buffer and write that out the disk then when that's done we can go ahead and get and fetch fetch the N pages right again that dis right might take a long time so that would be slow
36:24 so instead if we have the double number of of memory uh we need for the inputs and for the output buffer that we can have uh the system again fetch data in like we did before merge that out but while it's doing that dis right we're going and fetching the other data for the next the next sort of round bringing that into memory and then sorting that and writing that as well and again you're ping ponging or alternating back and forth to keep the system always running and doing useful
36:50 work so all this this reduces your effect of IO or sorry effect of memory that you have available by half if you're is really slow then this is going to be a huge win because you're hiding the that that disc all by still doing useful work and this is why You' want to use a you know a disc manager with non-blocking IO so you can say here's the data I want you to write out and have whatever thread do that right for you then you can go go have your worker thread go process more
37:19 data if you're relying on a like an osis call to do that like the osis call is going be blocking so you don't want your main worker thread to be blocked on the on the on the operating system why is doing the right the flush you want to be doing other things
37:34 yes can you triping sure yes but some you run out of memory is the technique you PR yes it is it commonly use I I don't know I think I think P does this I don't know about it MyQ
37:55 others again if your disc is like super fast then like it's less it's less helpful okay so one indal thing we really talk about uh another way to optimize this is the thing you wouldn't really think would be an issue and that is actually comparing the keys can be expensive again just going back to like CS 101 when you first Implement quick sort you're taking two 3it 32-bit numbers and just going you know comparing less than and greater than
38:26 that's a single instruction in the CPU that's fast but data isn't always going to be you know fix fixed length values and so you want a way to to to optimize that comparison because you can be doing a lot of that for a really big data
38:41 set and then you want don't want have to reimplement your sorting algorithm over and over again uh to have all these different variations of of possible data types so instead what often happens is that when you call your sort method or sort operator in your database system you also pass a pointer to the comparison
38:59 function now what happens then when I'm when my system's running I got to do a jump call to go to my comparison function to do the you know compare the less than greater than to then return back 01 as accordingly that jump call is going to be expensive on Modern CPUs if you're doing this again for a billion
39:16 times so there's some a two ways to make this go better go faster is one through code specialization we'll talk a little bit about this when we talk about query execution uh after the after the fall break but the idea here is that instead of having this general purpose sorting algorithm where you have it pass the function pointer and then make the call to the function to say do the comparison
39:37 it's better off to inline or hardcode that comparison operator based on the type so then now it's just all inline uh when I do my comparison and not making that jump call so if I know I'm going to be comparing two floating Point numbers I could have that floating Point instructions directly inside my my sorting
39:55 algorithm so there's a couple different ways you can Coen this you can do this as at like at um at runtime based on the data type Cen the the Sorting algorithm with with the inline function right or you can do this at compile time this is what postest does it's a bit of a hack but it works they have a pearl script that takes their sort sorting algorithm implementation and just duplicates it and makes multiple versions of it one for integers one for floats one for
40:21 whatever so in now compiled in the in the system they'll have the different flavors or variants if you will of the of the uh of the comparison function again think of like templating C++ but post is written in C so that's why they're duplicating the code so then at runtime I know what data type I have that I need to compare when I do my sort and I make sure I call the Sorting ALG that has that has the hardcoded comparison for that data type and now there's less IND direction there's not this this this jump to the the comparison
40:49 operator another tick we can do for really long uh varchars or strings is similar to what we saw when we talk about B plus trees where instead of having to compare the entire uh entire string to see whether there's a match maybe pass that data around I instead could just Lop off the a prefix of the key sort based on that
41:11 and then have that in line be really fast where I maybe have to look at the first three characters of of a really long string and that's enough for me to figure out whether I want to go left or right as I'm sorting
41:20 things and then if if the if the prefix or if the the prefixes are are equivalent you still have to way to back out call the actual full comparison operator or comparison function I don't know what uh systems do this uh this this typically mostly appears in maybe some the the the commercial systems or so the for for olap
41:44 stuff okay so she brought up the question of like okay what if I had the primary key or secondary index uh can I use that to make sorting go faster the answer is yes if you if you have a index a order preserving index like a B plus tree that's already on the keys that you want to sort in your order by claws then it doesn't make sense to sort that again because it's already sorted for
42:07 you um some systems like post can do this but they have to have an exact match like if I have my my my order by Clause is on is on uh columns A and B I have to have an index on On A and B in order to to to use it in Oracle and the Enterprise systems if my order by CLA is on a and I have an index on a I can still use that index because I know the a values are going to be sorted correctly or in the order that I want
42:34 but postgress again as far as I knows has to have an exact match so now again get the data we needed in sort of order it's just a matter of jumping to some point in the tree scanning along Leaf nodes and we get back the data I want but depending on whether the data is clustered or unclustered based on that Index this could be a good idea or a bad
42:53 idea just as a reminder when we talk about cluster cluster uh indexes theide is that the the the the the pages where the tub is actually being stored are in the same order as they as as they they exist in the leaf nodes of the of the index right so now again if I want to go get all this sort of data I just sequentially scan along the leaf nodes get all the pointers to jump to the data I need and again I don't have to do any additional sorting it's already sorted for
43:19 me right that's easy to do that's really fast if it's unclustered uh then it's the problem we talked about before where I may end up doing bun of random IO for fetching pages in out of order and having to go thrash and bring them out to bring them into memory throw them back out and read them back again uh if I'm not careful about this so for top end queries where I only need to get the the the you know certain number of values across the entire set then this is probably okay because you know the end the number of Records I need should be subset or much less than the total
43:51 number of records that exist so I can maybe just jump to one side of the tree scan the first couple uh first keys that I need and go fet those pages again different systems will do different things uh if it's index organized uh storage where the leafes actually store the data itself then this this isn't is isn't an issue again assuming that the order by Clause is based on the the the key that this thing is sorted
44:17 on yes question is like it's good for top end queries because if it's small then it's small Pages yeah so like if I only need to get the top 10 things uh so assuming that this is in uh say descending order right so that the highest value is going to be on this side I jump to that side of the the the tree you Traverse down and then SC along Leaf get the 10 things I want and then go f to those 10 pages versus like if we did the the the top end Heap Sort I got to scan all the pages because I I don't know where it's actually going to be stored
44:58 right even though that's one pass better than ex merge sort going get the index and getting exactly the minimum number pages I need is always be better yes is there a case that we actually want to use cluster B plus because this seems like a bunch of random I to me question is is there any case we would actually would un cluster B plus three for sorting no like for anything for anything compared to Cluster B plus uh so question is like the question is when would you ever want to use a unclustered b plus3 most systems use unclustered B plus trees
45:28 right for index organized storage like my SQL and I think SQL Ser can do this and SQL light like the the leaf nodes are the data itself right so this not an issue in in other systems like SQL Server you can say I want this or an oracle to I want this thing to be sorted based on the on the uh you know on the index in postgress you can call the cluster command and it'll sort all your data but it's not guaranteed to be synchronized so it do one it do it'll do external mer toer all the data basically rewrite the
45:57 and then over time if you update things it could get out of order but the idea is that first P kind of keeps things uh get things sorted at least initially and we haven't really talked about this there if there are tricks you can do if you know the data is semi sorted then there's some you know some tricks you can do say Okay I I I know that it's sort of enough and therefore I you know I may have to look at less data than I actually need
46:21 to but Mo most indexes when you when call create index will not be a clustered index is question is is it because the B+ Tre is only used temporarily uh if I call create index it's not temporary different
46:49 index maybe you're asking why aren't why isn't everybody doing a clustered clustered index and why isn't everybody using index or organized storage right it's a design choice of when you built the system whether you want to do that or not based on what you think that the the workload should be right so postgress was invented in
47:07 1984 uh I don't know whether index organized I I don't know whether the idea of storing data in the leaf no was was even the thing back then my SQL first my SQL didn't do that it's only ANB did that that came around like 99 SEL light is 2001 so it might it's a it's a semi- newer technique
47:27 but to your point if you have a bunch of like the idea is that you have the heat pages of the where the tupal are that's unsorted and then I can build whatever indexes I want right and that might change over time I might say okay I most my queries need to be data sorted in this way so I build index for that and then over time it may becomes another column becomes more important and you want to build index on that again that's the great thing with relational model and seal is that you can make that change without having to maybe throw everything away the index organized storage kind of kind of uh makes it more obvious the or exposes to more about the underlying storage mechanisms of the of the data because now you know it's going to be sorted based on the whatever you specify as the primary key for the cluster
48:08 index but that's that's more philosophical like whether you want to design your system to do that or not Oracle and SQL Ser will give you the choice like you can do things unsorted uh you can have un un unsorted heat Pages or you can have index coordinated Pages you can specify on a per T basis which one you want to use my SEO with NB always does index organized
48:32 storage okay so now we going talk about aggregations again sorting is going to be a backbone uh be one potential way we can implement aggregations but hashing is going to be the other one and we'll focus more on hashing uh techniques next class right and this is like a you know the the Bloods with the CPS like this is a classic trade-off between these these rival approaches to like making your your data system fast right sometimes sorting algorithms would be better sometimes hashing algorithms would be better and then if you look at the the lit research literature over the last couple decades sorting was faster then Hardware got better then har then hashing got faster then like the algorithms got better for sorting so s like it goes back and forth but in general now nowadays the the hashing is almost always going to be better but
49:16 we'll see this next class there may be times where the the the the the query has an order by Clause it needs the data to be sorted and just so happens that if you sort the data uh once with then you can do your aggregation very very quickly without having to do the hashing
49:33 technique right like the byproduct of like getting the data sorted so you can do aggregation ends up satisfying the order by clause for free and so you get a big win by just doing do doing the two together but in general hashing always is almost always going to be better especially if your disc going to be slow all right so again we talk about aggregations in lecture two but the idea was we have some some collection of data
49:55 and we want to do some computation and collapse it down into a single scalar value like a count min max sum so forth and so what we're going to need is in our system is we need a way to quickly identify that tup have the same key like whatever whatever it is that group ey is based on so that we can put them together to compute whatever aggregation is going to
50:16 be so let's start with the most simplest uh aggregation function distinct it's give me all the unique values for for a given column and this example here I have the order bu on the on the course ID and myin Clause is going be the course ID so in this case here sorting is going to give us you know kill two birds with one stone because we'll get it sorted for the orite and we use sorting for the for the stink so let's say now we we do our our filter based on the wear Clause get down the the the minimum number TOS we need then we do our projection to remove all the columns we actually we don't need and then now we just sort this using actually a merge sort and then now we just have our our iterator go through our output of the sort of data just check to see whatever the cursor is pointing at is it the same as the last value I just looked at if yes I know I had I I I can go ahead and remove it and that removes all the
51:09 duplicates so that that's pretty simple right pretty easy so if we don't need the data to be sorted uh then forming the groups you know uh it may be actually beneficial to use hashing because you can sort of quickly identify where things are and check to see values whether they're equivalent to whatever you are trying to do like a distinct or whatever the the aggregation is going to be it reduces the removes the problem having to do maybe sequential scan to look at all the data find you're looking for especially because again if you have to spill a disc when I'm trying to find a duplicat if I have a bunch of things that I've had to spell at the disc because I ran out of memory I don't have to go fetch those things back in to see whether I'm the same or
51:50 not so in this scenario hashing almost always is going to be better not I mean not almost always always uh if I don't need to be data dude uh because I can again do the same divide and conquer Technique we saw with with the external mord where I can break it up to sub problems that I can bring into memory now right a small portion of the data I can bring into memory do whatever the computation I need on that on that data wilds and memory and I know because of the way hashing works that there isn't going to be a key that I shouldn't be looking at that that I missed that's on some other page that's out on disk
52:23 because if it was equivalent to me and therefore I cared about it it would have brought in put in the same bucket that I went into right and this is almost always going to be way cheaper than having to sort things ahead of
52:36 time so the way we're going do hashing aggregation so we're going to first populate a an a hash table for the for the query that we'll start putting our keys in and depending on what the computation is the value will be like a running total or Computing a sum or what you the M max value course whatever whatever it is and then now as we scan the table we'll go check that hash table see whether our key already exists and if it does then based on what aggregation is going to be we determine what to do like if if it's a distinct and our key already exists in this hash table we just we throw away our key because we know it already
53:10 exists so again just like before if everything fits in memory then this is easy to do I scan through the data once populate my hash table and and I'm done but again if the hashtable can get quite large then this this is going to be a problem so we want to be able to be smarter Again by spill a disc and doing a divide and conqueror
53:29 approach and we want to make sure that we minimize the amount of random IO and try to maximize the sental io so this is what external hashing aggregation will do for us so it's going to have two phases and the first phase will be a partition phase we're going to just scan through the data once hash all the the the tup we're looking at based on the you know the aggregation key like the group by Clause the key and then we're going to write it out to unordered buckets
53:56 and then if if that bucket gets full then we just we just write that out the disc and use use another one so we're going to prepare the data ahead of time by dividing up into these partitions and then in the second phase we'll just bring these partitions in one by one and do whatever it is the competition we need to do to produce our final output and again because we've hashed them such that keys that are the same will be in the same bucket and the keys that are that are aren't the same may not technically be in the same bucket then we know that there isn't again some other bucket we should be looking at to find a match for that what we
54:29 and this will maximize amount of iio we have to do so again the in the first phase the partition phase we'll have we'll have one hash function H1 to split the two BS up into partitions and then if the uh if the partition gets full then we just spill it out the dis and write it out and then again reuse reuse the memory so assuming we have B buffers we're going to use B minus one buffers for all the partitions we're bringing in
54:54 I sorry for the output buffers and then we'll use one buffer for input and again obviously you can paralyze this by using more buffers and some point but the basic algorith is it's the opposite of what we saw with the external merge sort was I had to have B minus one buffers for the input and then one buffer for the output this is I use one buffer for the input and then B minus one buffers for the
55:17 output because like in s of merge s the idea was you're you're bringing in uh you sort of have a fan out of data you're bringing in and you're callusing down to sort of you know one stride of data where this is the opposite I sort of have one piece of data and I'm I'm Fanning it out because I'm that's what the partition the hashing is doing for me so going back here uh again my query now doesn't have the order by Clause so I would but I want to get this distinct
55:41 so in the first pass I do the filter and then I remove the columns and then now in the first pass of the the external hash aggregation I just scan through whatever the data I have here I run it through my hash function and then I start filling up these buffers and just writing them out sequentially and say this guy here he gets full well I just to go ahead and write that out the dis and reuse the memory for for the next
56:02 the next uh for any other key that gets hashed into this and I'm not going back at this phase of the algorithm and going looking at whatever I just wrote back out once it's out the disc I'm done with it until this phase is
56:16 done then now in the second phase I'm going to bring those those partitions in uh and I'm going to Hash them again and write it now to an M hash function or hash table and the idea here is that my
56:29 hash table is will be small enough to fit into memory for the for the the set of uh buffers that I'm looking at and then once I'm done with Computing whatever I need for that uh s set of buffers I can then populate a new hash Table after I write it out to the fin the first hash Table after the final result so again it's a divide and conquer approach I'm bringing in the data in in smaller smaller chunks and I don't have to go look at other data
56:54 that's not in the chunks I'm looking at and and so therefore I I can compute whatever answer I need just on that data so meaning once I fill my hash table and I I populate it I know I I don't need it again to ever update anything else because I'm not going to see any other keys that are hash into the same uh have have the same keys in the first hash
57:13 table so in the first page here again we going to bring in all the buckets we have for the the first chunks right and the B minus one partitions and now I'm just going to sequentially scan through these hash them install whatever the the the the the key is in my hash T again this case here I'm Computing distinct so I don't there is no value just like does this key exist or not right it's basically a set so then I keep scanning along do the same thing hash ENT there
57:36 then I get down here hash there when I'm done so now for these B minus one partitions when I'm done right I can take whatever exists in my hash table and now produce portion of my final result that I'm going to send back to the
57:50 client then I can keep contining for all the other partitions that I have hash it fill fill in a new hash table and when that's done then I write you know it writes the final result out to uh to to the um to the client again whether or not the final result and the hashtable merge together which is just right it in this phase here again depending what aggregation is I need to quickly do a you know a random IO a random lookup into the hashtable so since this I had the mechanism to go find this I don't want to actually use the final result as my hash table but I can just scan through and find all the keys and and produce my output that way
58:28 so this is distinct distinct is easy does the key exist or not for the and for for other aggregations we'll talk about a second like the value push in this hash will have addition additional summarizations as we go along so what do we do with this right again instead of having to do sequential IO to go look at everything maintain some potentially giant hash table to see whether I have matches I'm breaking up to smaller problems uh smaller chunks of data and then now I just have a bunch of squential IO to go through the data once I've divided it
58:59 again going back here once I finished with this you know these these buckets I never have to go back and check it again and because in the first pass I've already hashed them I know that down here in additional Pages there isn't going to be another 15445 because it can't exist because if it did it would have been hashed in the same location that I did so there isn't going to be some random thing down here that would cause my aggregation to compute the incorrect
59:24 result yes question like why why do I have a separate hash table for like for this phase and then I throw it away and make a new one because I don't need the memory for the first hash table and it might be
59:40 large right yes is there is there anyit of having multiple rehashing phases some like merge question is is there any benefit of having multiple rehashing phases yes so we'll talk talk about this uh next class but it may be the case that this thing if there's a ton of people in 1545 this thing gets really really big or let's say not even a bunch of people 1545 say like a bunch of keys all hash into the same set of buckets
1:00:08 then what you want to do is another round of H of repartitioning where you pick another hash function and hopefully that divides it up further you just call recursive hashing we'll see that next class if your data is skewed you'll have that problem you need it to handle
1:00:23 that okay so for aggreg s um again the basic idea is that instead of having you does the key exist in this my output hash table I'll have the the key point to some some total or computation that that I'm maintaining to again compute the final a aggregation that I need so now depending what the aggregation function wants when I do my probe my hash table and I find the key that I want I update this running value that I'm maintaining accordingly as needed
1:00:52 right otherwise if it doesn't exist Then I then I install it so going back here say in this case here I want to get the the the average GPA of students based Group by and course ID so now again ignoring how you know I'm going through this sequentially but assume this is this is all sort of happening uh you know one by one in my hash table now I'll have the key that that I'm hashing based on the the group ey the course ID
1:01:15 and then the value will depend on what the aggregation is so in this case here they want the average so I'm going to maintain the the number of keys that I've seen the count and then just uh a running total to the summation so then when I when I went and then produce the final output uh you know that I return back to the client I just divide that running total divided by the number of records that I've seen number of keys that I've seen and then that produces the
1:01:40 average M and Max is maintaining the highest and lowest I've seen right sum is just counting things up and counts just incrementing everything by one like all aggregations could be can be computed in this manner okay but again the main takeaway here is that hashing is going to be better for us when we have to spill a dis uh than than than than doing sorting because I can still do the divide and conquer even though it would normally be random IO
1:02:09 but because I break things up to smaller chunks I can still get s w out okay so next class we're going to talk about joins but we'll see more again the difference between the benefits of like sorting versus uh versus hashing into Co joint joints will be super important that's most it's the where typically data are going to be spending most of their time uh to compute joints that's for really large tables
1:02:34 so the the optimizations we discussed so far sorting like things like chunking I amortise cost do the double buffering a lot of those techniques will also be applicable for us when we do hashing or start doing joins and other computations we could potentially want to do in our database
1:02:50 system okay uh yes Bas has have like first would do the first scin and distribute them into buckets um does it have to be one distinct key per bucket uh so question is in phase one of the the the partition phase when I'm doing the the initial pass the first hash function and writing these out the data out here does the keys have to be distinct no because again you can have collisions based on your hash function
1:03:20 that's fine what I really let's go ahead for the second round we can't have uh is and then for the second round can I still have hash collisions yes right it's the same this is just a linear prob hash table we talked about before pick whatever your favorite hash has table you want cucko hashing whatever right you're still going to have collisions potentially and then the the the hashing scheme then tells you how to handle the
1:03:45 collisions right so in my my example here yes I'm showing you that like this thing Maps exactly where it was but like it could have hashed into this and I I know that this thing's occupied SC down find you know find the the first free plot to put my data
1:04:00 in again just think of like the the the things we've talked about in the previous lectures are the building blocks we use to do more complicated things so we already know how to handle conflicts in in our hash
1:04:11 table it's it's the same mechanism here it's not special any other questions yes her question is where's this final result actually being stored and as I said like the reason why this the this thing can't be this because this is some giant hash table right and I don't want to send back the hash table to the to the to the client because they're not going know how to deal with that so where is this thing actually being stored so you would have to allocate some output
1:04:44 buffers uh technically inate results so like what think of like in the query plan every operator would have a little output buffer or start filling stuff in and depending on the implementation of the system you could start sending back results to queries to the query or to the like as soon as you get something in here because you know there isn't anything you have to do after that but most of the times it's it's like a blocking call like so once you have the entire output buffer filled in then you return all of
1:05:12 it which means of course again you could run out of memory when you start filling in your Apple buffer if you do like SL if you do something stupid like select start from table with a billion records with just getting everything back then yeah you it's going to start going slow because it has to start paging as you as you start writing out the the the buffers over the the wire protocol and that's like most systems will have like a a built-in export functions so you don't do that so you can kind of stream things out uh ex
2. Jump to
1:05:39 talking about DBT too all right this is Drew he's the co-founder of uh DBT as I said you don't know you need DBT but you will okay and that's not me pitching intro yeah thanks Andy and hi everyone um so yeah my name is Drew from DBT Labs I have an iPad and apple pencil and I'm inclined to use it so this G be hopefully a fun and quick presentation about DBT uh my contact info is here would love to hear from you uh if you're ever interested in chatting I live in Philadelphia um and I love mentioning
1:06:08 this I did not get into CMU I did apply I did not get in um cool so I want to kind of talk through uh a story here and part one of this story is you know the promise of analytics and business intelligence and so the way the story always gets told if you talk to you know honestly lot of vendors is you have tons and tons of data sources uh that represent data about your business so it's your application logs and your you know payment providers and your customer success tools like people opening tickets things like that and so the promise is you can extract and load all of your data from those sources and load them into your cloud data warehouse your single source of Truth and that will unlock bi and analytics for the entire organization and make every own Super efficient and productive and it's going to go great um and so this is the promise that that we often tell people about
1:06:56 analytics the reality is that you get something that looks more like this um so these data sources represent thousands and thousands of tables some of them are up to date some of them are not like some of them are deprecated meanwhile you have different Engineers creating lots and lots of other tables kind of as derived data sets or or maybe their views and I kind of make a joke about this here but it's not that much of a joke uh you're going to find a table at some point in your career called something like prod.
1:07:21 VW XR F 30d V2 John and it's Mission critical for the business and nobody knows who John is because he stopped working here like 10 years ago it's powering these Mission critical dashboards and reports and operational tasks that are you know critical to the functioning of the business and yet you have no idea how it works you're afraid to touch anything because you might break it and all the people who knew you know what any of this stuff does left a long time ago um and so the the actual computer science term for this is I think an fton of tables is how we refer of
1:07:56 that um so there's some real problems here right there's no data lineage we can't tell where data is coming from and so we can't trust it is this up to date was this built by someone I think is reputable or someone I think is like not very good at their job or someone who uh uh doesn't understand the domain things like that there's no data documentation right it's just tables in a in a data warehouse in a database um so you can't reuse any of this stuff it's hard to build on top of it you don't know if it's going to change out from under you or be there next week um there's no deployment process for any of this stuff it just exists in the database people just create tables and Views ad hoc and so as a result you know everyone just develops in prod and that means that you're going to break stuff in prod and then you're GNA have a hard time undoing it um so really not much in the way of like mature software development um workflows happening here and of course you know there's no quality assurance
1:08:46 when you're editing stuff in prod uh except you know crossing your fingers that's part of it so the result there is you break you break people's dashboards um the CEO hates when when that happens right and um finally kind of the the root of all this is you get this really fragmented business logic so if I come back to this image the logic that defines you know information derived from your data is spread out across hundreds or thousands of tables you can't actually understand the reality of how we calculate a daily active user or weekly active user
1:09:17 because it's spread so far and so wide and you know as far from centralized anywhere so all in there's a lot of problems here and they have really meaning negative impacts for the business or let me say the organization in general um but fortunately you know there's a lot of good and well understood Solutions here so the first one is you know we think that you should Version Control your data Transformations so if you're building derived tables you know from your your Source tables loaded by um loaded in your data warehouse if you Version Control those Transformations then it becomes really easy to you know View and change business logic down the line as your organization or business
1:09:51 evolves if you can visualize data lineage then you can understand how data flows and figure out if you can trust a table so maybe if I'm looking at a customer satisfaction score metric I can understand if that's coming out of zenes our customer success tool or you know a a Google sheet that we set out to 47
1:10:10 customers last year uh where's where's this thing coming from okay uh we always recommend using a cicd process this continuous integration and continuous deployment uh if you're not familiar the big idea is that when you you know effectively open a PO request in GitHub or get lab something like that you can test all of your changes and make sure that everything's passing and then when you merge those changes they'll be automatically deployed out to production right so having automated deployments is a key tenant of a mature software development workflow we think that data people should work the same way and one of the big punch lines here is you get to develop in Dev not in prod which is you know where you should be
1:10:45 developing automated tests are a huge deal this helps you find out if your data is broken before your CEO finds out it's okay to break things as long as you fix them before people find out or if you communicate well uh well while it's broken um but definitely you don't want to find out that you have a problem because you know the CEO saw first that's a bad way to find out okay last and it's very important to document your data sets right you're doing all this work to create dve taes that represent some sort of transformation of data some sort of business logic rule that you think is important you should document that so that other people can build on top of your work and so you can sort of collaborate instead of all you know uh stepping on each other's toes and and uh building things that have already been
1:11:27 built so I just want to show you some screenshots of uh how this works in DBT um this is our kind of approach to lineage here which is pretty cool so we can see these I don't know if it's going to come through on Zoom so well but um these are like Source tables so these are loaded for us by a tool called five Tran that extracts and loads data from in this case uh stripe our payments provider so this is data Landing in our data warehouse which is Snowflake and then all these blue nodes here in this lineage graph are transformation that are kind of stacked on top of each so we only need to solve some of these problems like one time and then we can build on top of those derived data sets
1:12:04 um and then you can see lots and lots of interesting information here um like where the table lives in the database for example and this is a table called you know dim stripe customers so I talked about version controlling your code this is DBT approach to doing that and basically what it looks like is you create you know SQL files in a GitHub repository
1:12:27 and these SQL files are mostly SQL select statements so um this here is a that's a Common Table expression if you're familiar basically it's just a SQL select statement and the only big difference between DBT code and pure SQL is that we have this templ templating language called Ginga that allows you to refer to another table or in this case another source so um this reference to a source table called GitHub stargazers is how we automatically infer the kind of lineage that you here so you don't actually have to go and Define lineage yourself you just reference another
1:13:00 table cool I just want to show you a couple more things um we talked about automated testing this is pretty cool this is that same table we were looking at earlier I think dim stripe subscriptions dim is short for a dimensional table and um the big idea here is that we can run these tests like in this case not null I'm sure this is really small on your screen I'm going to try to help you and I'm sorry if you can't see it um so not null
1:13:26 strip subscription subscription ID so a database like snowflake doesn't actually enforce you know uniqueness and not nullness constraints um most like data warehouses comary data warehouses don't actually enforce constraints but they will use them to optimize queries uh but it doesn't stop you from putting n null values into a a column or duplicating values in what you say is a primary key column so that's kind of scary but you know with something like DBT you can actually just assert I expect my subscription ID column to be unique cannot null and then DBT will check for you and in this case you know the test pass which is great and so if ever you change your transformation logic in a way that violates this constraint or if you get new data from the Upstream
1:14:08 Source in this case stripe with duplicated or null subscription IDs will alert you you'll get an error message and again you'll find out about it before your CEO does when uh their dashboard doesn't load okay and the last thing I talked about is uh the importance of developing and development instead of production and so this is an example of uh we call this the DBT Cloud IDE so this is an our SAS product uh DBT Cloud it's that same model we were looking at I'm sorry I'm saying model it's that same SQL uh code that we were looking at earlier except here it's an a kind of integrated development environment so this makes it easy to build this derived data set um
1:14:45 run your tests check out sort of the preview results of the query and uh manage all the files in your codebase commit them with Git and GitHub uh and it you you know our goal is for it to be like a One-Stop shop for developing your your DBT project so ins some you know our goal is bringing software engineering best practices to data teams
1:15:04 um I know that everyone in in this room is a computer science person and so that might feel obvious to you but I'll tell you that is usually not the case out in the real world you get a lot of people doing a lot of random stuff in the database and I'm wondering why it's uh why it's all not working okay awesome
1:15:23 Applause all right any questions for Drew yes will the test be expens his question is will the test be expensive for like the that you show would that be expensive to run to run you're running lot of you're running lots of data would it be expensive I mean Drew you want to answer that yeah totally uh it can be I think a lot of the power of DBT is that we run the queries that you tell us to run uh that also means that if you do something inefficient it can be expensive and I heard you say if you try to select star from a billion row table it can what overflow your Alpha buffer or something like that like same rules apply so we have tons and tons of cost optimization
1:16:06 stuff like only checking the last seven days of data for uniqueness not nullness for because because you don't need to check very old data just say if you've already checked it so lots of faculties like that in DBT Club so I'll say Drew can't say this but I'll say it they're not hosting the data so yes it could be expensive they're not paying for it right no if you're the customer it's your snowflake database you control it
1:16:28 you're telling DBT make sure this data looks good and like yeah it's expensive but like there's a lot of cases where you know fat finger mistakes or mistakes in data cost people millions and billions of dollars so yeah you it's worth worth paying
1:16:43 for any any last question the worst table name I ever saw was uh uh they had it was called table one uh and because they had table 1 2 3 and then there was table one real and table one uh old and the production one was table one
1:17:00 old that was the worst okay right let's give another round Applause I need something refreshing when I get finished manifesting to cold a whole B like Smith and Wesson one court and my thoughts hip hop related write a rhyme and my pants intoxicated
1:17:18 lyrics are quicker with a simple Mo lier since on mer City Slicker play Waves of picker RS I create at a we to quit to duplicate feel a Bree at a skate mik at fah when I holding real tight then I'm in flight then we ignite starts to boil I heat up the party for you let my girl me my mic down with oil Rec still turn with third Dee Burns for one man I heat up your brain give it a suntan so just cool let the temperature rise to cool it all with odds
1:17:54 oh