CMU Database Group · 1:27:09 · https://www.youtube.com/watch?v=4y656idl8ZU
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 lcks and M Clips the Chrome will make the average imitator do back flips you like a [Music]
0:27 pistol should not be this this in basically November that's not good all right so uh for everyone in the class what's on the agenda again project Three is out we do November 17th we've announced on Piaza or we will announce Patza we'll have the recitation this Monday coming up at 800 PM because Tuesday supposed to be an off day for everyone but then homework four will be do uh this this November third coming up okay any questions about project three or any questions about homework four is it depends on Project a question project three project two uh there is you have to do index scan and an index n Loop join that would use your B+ tree if you can't make it concurrent just put a put a fat latch on top of the whole thing
1:13 right that'll just protect it it like and then I don't I don't remember what the the leaderboard is but like uh that that'll be sufficient get for correctness okay all right so uh where are we at in the course so we we made it to the top like last class was about query optimization right so we now know how to do query planning like now we know how to take requests from the application to you know for SQL queries convert it into
1:42 uh to to a physical plan and execute it and we now know how to execute whatever The Operators we pick how to access the data how to manage memory coming in and out of disk right how to organize things on dis like so this point in the semester you you can build a End full endend database system yes haven't covered the parsing part of the question you haven't covered the parsing part of the query uh I don't care about that uh no no no so like there are like that's a solv problem there's open source libraries to part SQL use one of those
2:14 right there's there's SQL Parts in uh in Rust there's Li PG qu Li PG query in for C++ or C just use those right it's taking that a binding it to optic IDs in the catalog and then running through the optimizer the optim that's the hard part
2:30 so where we need to cover now though right yes we can build a database system that can run queries and store some data and return results but we haven't talked about what happens when the thing crashes how do we make sure we don't lose any data or what happens if we have two queries trying to update the same thing at the same time What do we do so overarching across all of these these different layers is going to be what we're talking about for the next three weeks is the concurenti mechanisms which we'll start with today how do we make sure that transactions or queries are updating things in a safe Manner and then there's a recovery piece which will cover in in two weeks uh and that is like if my databas system crashes how to I make sure that I don't have any corrupted data I don't lose anything
3:10 right because again if you start you know what what good is a database if you write things into it and then it just crashes or the system restarts and you lose everything that would be bad and the reason why I'm sort of showing these as as these these layers that are uh overlapping with all the other parts because as we see as we go along that all the design stations we have to make in our different layers have to take in account into you know what concurrency protocol we're going to use or how we're going to do recovery like your buffal pool manager needs to go back and says okay well what transaction updated this page is the log record for that page written out the dis yet if yes I can evict it if no I have to wait so the additional logic and the eviction policy we didn't talk about because we haven't talked about logging yet and recovery so that that's what we're going to head into now
3:53 okay so uh let's talk motiving example what transactions look like let's say we have a really simple location uh that that it's the ATM at your bank and you basically the logic is somebody wants to take out some money you got to make sure they have at least have that enough money that they want to take out take it out of the account pay it out basically transfer it out to somewhere else and then right back into the database and say okay they took out this this amount of money right so you can sort of think like the application logic would be like this but the steps we would do it in the system was that we would read what the current balance is for a check to see whether it's sufficient funds if yes then we can go ahead and pay out the $25
4:31 or transfer $25 to somewhere else but then now we got to deduct the the the amount we took out to our new balance and then write it back to to the database and update the state right so this is sort of a high Lev operation that you would want to do in your data system like before we were talking about like these are SQL queries it's sort of think like even more high level than that like here's this is some
4:54 piece of work I want to do to perform some operation and it may compr be comprised of of multiple queries or additional application logic all right so the first problem we got to deal with is well what happens if we crash
5:07 here right so we check we read read the bank account balance had $100 took the money out uh transfer somewhere else but then now we crashed before we wrote it back right so in this point what should the state of the database
5:25 be right should it be the $25 I took out is that be accounted for right well say say instead of pay $25 I put $25 into somebody else's account right are they going to have the $25 and I'm and I'm still going to have my $100
5:39 that would that would be bad right because we we end up losing data corrupting the database or let's say another situation like this say you and your and your best friend share accounts for some weird reason right and you both want to take out $25 at exactly the same time so the logic here is going to exed twice and say like two different workers or two different machines it doesn't matter so both can read the balance yep we have $100 uh so we go ahead take the $25 out transfer it out and then we go ahead and update the New Balance we $75 and then at the exact same time they both write it back to the
6:13 database is this correct no right because now like there's a magic $25 that went missing from the bank account uh because two people try to right back to the same thing at the same time right individually they were correct right they did all the right steps to see whether I have you know sufficient funds yes if yes take the $25 out transfer it somewhere else and then write it back out but concurrently a running time mously then we have this weird effect where money went missing and that's
6:45 bad so how can we avoid this problem what's that use a right he says use a right latch what right latch on what on on a question is there way to do that yes we won't call them latches we call Locks but that that is one way to solve that problem that's next that's the next
7:10 class so what if we did something like this what if we just said that we don't allow queries to run simultanous or transactions to run simultaneously at the same time that we have some kind of q a single q and one worker that pulls out one transaction at a time one piece of work at a time executes it to to to completion
7:30 right and then when it's done then it's allowed to go execute the the next thing in the queue all right that solves the problem of of of the second example where I had two guys sany trying to update the same database the same record right now that won't happen because only one thing can run at a time that's essentially the right latch that he's proposing the right lock right it's a single threat
7:50 execution but now what about the problem I said before where the in the first example where I I did an update and then I crashed before I was able to get the money back to the account but what if I did this what if I
8:05 before any transaction starts so I pull out of the queue what do I just take the database file right assume it's a single file or directories doesn't matter and I make a complete copy of that data then have the transaction operate on that copy and then when it says okay I'm done done all the work I just now flip a pointer to say the my copied version is now the new version of the database so anybody any other transaction that comes behind me we'll look at that new version and then I I'll discard the old version later
8:34 on if the transaction fails for some weird reason and we come back well we just see that we have this this copy that we modified but we never actually fully saved it so we had we can go ahead and just ignore
8:47 it so is that correct will that that would avoid update problems so can head yes is it a good idea no why not parm say it again parm he said the Mount of parallelism is is basically zero sure but it's correct though right and a lot of in most cases any two transactions don't actually share he says uh in most cases two transactions don't actually share data yes you can just paralyze
9:24 them it said that you paralyze them because um I would say that a lot of times in in transactional systems there's a there's there's a hot set a working and that's like think of like when you go to like Hacker News or Reddit you post comments on like whatever's on the front page
9:40 right everyone's trying to update that one like the small set of things so that usually there's a hot set what everyone's trying to update or modify right uh the example I used to do give was like Taylor Swift's Twitter account or Justin Bieber's Twitter account like those would be they actually would run on separate machines because they would have so many people trying to update or read at the same time so usually there's hot records that everyone try not modify
10:01 uh so it's not always true that they that every transaction would be uh you touching distinct things he said she says it's not scalable correct yeah so if your database is 10 megabytes or say the smallest case four kilobyte page sure no big deal right copy it do whatever you want write it back if I got one petabyte of data then I don't want to be copying one petabyte every single time now there are some file systems allow you to take uh like an xfs you can take uh Delta snapshots or copy and right snapshots that are really fast but in general this this is not going to be a good
10:34 idea right so this will be correct but and some system will actually will do this the one of the first systems relational Data Systems system R they did this it's called Shadow paging we'll see this in a second uh but you know it has a lot of problems that we'll cover as we go along so the problem we're trying to solve today is that we want a better approach than just having transaction run one at of the time and we want a better approach than having to make an entire copy of the database as like a shadow copy or or like a a dirty version of it we don't avoid all that extra overhead and what we want is we don't allow transactions to run concurrently
11:15 and be clever about how we inter leave their operations their queries so that we can maximize parallelism but still also ensure correctness right I it's pretty obvious that we'd want this right if if have one transaction that blocks it has to read something from disk or write something from dis we can let another transaction run at the same time or modern CPUs they have a lot of cores we want to you know we want to be able utilize all of them
11:39 we see in some cases some systems like sqlite they'll allow multiple readers but they only have one writer at a time and that makes certain things a lot easier uh but in system like postgress and MySQL and pick your favorite you know transaction data system they're going to allow multiple transactions around the same time because you just get better
11:57 performance so the way to understand or sort of State set up the problem we're trying to solve today is that we want to allow this arbitrary interleaving of operations I I'll find what they are in the next slide uh but think there's reason rights we going to arbitrarily allow them to to to to run simultaneously but be be smart about how we schedule things so that we end up with a state of the database that is
12:22 correct and I'll put big big quotation marks around correct because that can mean different things for different people but today we'll talk about serializable are serializable scheduling and that'll be like the gold standard say this is this is this will be equivalent to if I ran it in serial ordering but we'll see next class most systems don't actually do
12:40 that one important thing to understand though is that when we talk about transactions today that the database system can only control or only has purview on the things that it can do on behalf of the application and that's just end up being reads and rights and that means that we could Define a transaction that could do a bunch of steps for us but then if the applic says okay in the middle of that transaction let me send an email confirmation to you
13:03 right but then that something happens and the system crashes we got to roll back our changes and we got to run that transaction again because that email step is not controlled by the datab system we can't roll that back so we can only the only can only control whatever happens inside of us if someone does something on the outside like launch a missile we we we can't stop
13:22 that so we need a way to define what it mean to be correct and determine whether when we start inter leaving these oper operations within transactions whether that's a valid thing to do or not so for today's class we're going to talk about the database sort of in an abstract manner uh and we're not going to talk about tupal we're not talk about tables we're not to talk about any other things you have in a database system we're just going to say that we have objects we just a BC D and so forth
13:48 right it doesn't matter how you know what it actually is all the algorithms we talk about today and and going forward will still work no matter what the size is and obviously if the smaller you make it the more parallelism you have uh but there's more overhead and maintaining and tracking who has what or who's doing what for today's class we're also only going to we're going to assume the databas is fixed size meaning we have a fixed number of objects at the very beginning and any operation right operation is just going to be updates so not do we're not doing deletes we're not doing inserts those will cause additional problems for us we got to cover next
14:22 class so then now we're defin a transaction again in the con in the in the within the scope of data system we're just going to say transaction is going to be a sequence of read and write operations on these
14:32 objects all right I'm not saying whether they're SQL queries I'm just saying like I'm reading something and I'm going to write something I'm just overwrite the whatever the current value is transactions will start with this explicitly with this begin command uh in some systems you if you just write any one query that's all it's sort of implicitly there's a begin and commit at uh around it it's called autoc commit but for our purpose today we assume there's explicit begin that says when trans transaction starts and then the transaction ends when either the application tells us that we commit or roll
15:02 back and then we'll see this next class just because you tell the system I want to commit doesn't mean you're actually going to commit it's not until you get the acknowledgement that you know thing's actually been safe because in some cases you may say I want to commit and the data system is no no no you're not doing that and actually kills you
15:16 right and it's and it's allowed to do that according to the sort of programming Paradigm that we're going to expose so again today we're just going to focus on doing reads and updates no inserts and assuming the datas is a fixed size and then we're going to have explicit begin and commit
15:31 commands all right so the way we're going to determine whether a schedule of of transactions on a data Sy are correct is going to be through this notion of of of This Acronym called acid quick show hands who here has heard of acid before
15:44 all right halfish a little more half right and so this is a this is a acronym that was developed in the early 1980s uh by this German guy um and it basically stands for atomicity consistency isolation durability so atomicity is going to mean that all the operations within my transaction have to occur or none of them occur right all they're nothing
16:07 consistency is a kind of a weird one but it basically means that if my transaction does consistent things and my database starts off in a consistent State then when that transaction runs the data is be consistent all right well that's kind of fuzzy too right uh we'll cover this in more details later on but this will make more sense when we start distributed databases basically if I have do an update on this one machine and I have data replicated on other machines if I say this this transaction commits if I have the if I providing consisteny guarantees if I immediately try to read that thing I updated on another machine I should see that exact value or see the correct
16:46 value the truth is the guy that the German guy that kind of tried to came up This Acronym ad myy isolation durability this makes sense in transactions he kind of shoehorned consistency in there to make the acronym work and then also the joke go apparently he was trying to make fun on his wife cuz his wife didn't like sugar she's like oh she's an acid woman so they added so she got he he want to make sure he got consisteny in there
17:07 that's what the book says I I've never met the guy so I don't know that's true or not all right next one is isolation this will be really important we'll focus most mostly on this today this is just saying that a transactions will execute uh under the illusion that they have exclusive access to the database
17:22 and they're isolated from all the other transactions running at the same time and that means that we don't want to see any intermediate upd dates from transactions that may have run at the same time that we did and the durability one is pretty obvious it says if my transaction commits the datab system tells you that it's committed but then if the system crashes and when it comes back you should be able to see your your
17:44 changes all right so today's class we're going to go through each of these one by one and again this is just sort of the high level Concepts we're not really talk about any specific implcations or algorithm you would you would have in your database system to actually support these things that's what we'll cover uh starting Monday's class next week
18:00 and then today also too we have uh a guest speaker from Firebolt um last class or last week we had click housee which I thought was a really great talk uh firebol is actually a fork of Click house right so they took click house they forked it rewrote a bunch of stuff then they got one of the people out of Germany to go do a bunch of rewrites uh and they they've sort of diverted from being pure click house anymore so he's going to talk about the some of the stuff that they that they're
18:26 doing okay so we're going to go each each of these one by one so again atomicity again either all the operations are going to happen in the transaction or none of them right so there's basically when when you say a transaction is going to run uh there's be two possible outcomes that all the operations will commit in the order that the transaction specified um or he either gets uh aborted by the the application saying I you know go I I don't want to do what I just did roll back the changes or you go to try to commit and the D system no you're not allowed to commit I go ahead and kill you
18:59 so it's the datab system's job to make sure that all these TR actions are Atomic right and it's not something you specificate the wor about in your application code you just know this if I get a transaction in my if I set up a transaction in my system I should expect uh my operations to be
19:15 Atomic so there's two basic approaches to guarantee atomicity and again we're not going to go into too much details of what these are we'll cover these uh in in the following weeks the the first one is the most common one like logging and it's unfortunate that the term log logging is used typically like for debug logging like when you print out print statements uh when your application's running to try to figure out what's going on um but a logging would be a a way to keep track of like here's all the operations my transactions made while they're running and I'm going to write them into this almost like a ledger if you will and that'll actually can be maintained separately from the database itself or if you remember log structure mer trees right all the update operations were that was that was in this log same same concept same same
19:57 idea um you can think of this as like again the black box of an airplane so like if I crash the airplane crashes they go find the black box of of course all all the steps the plane was doing right before the crash same thing here if my if my do a bunch of operations my database I go ahead and commit uh and I know my transaction should be saved uh and all the effects should be atomically
20:17 persisted then I when I look at my log I'll see all those updates and I can replay them to put me back in the state I was before so I don't have any uh loss updates I said nearly every single dat system today is using uh some variation of logging uh you you get better performance in some cases we saw this in log structure merry because I can turn all my random rights into sequential rights uh and then also for audibility
20:40 or recoverability it also is super helpful for that the other approach is what what I talked about in the beginning this thing called Shadow paging and my my sort of straw man example was the extreme case where I copy the entire database into a shadow copy and then make any changes I want uh typically you would do this with with at a page level so anytime I try to update a page then I make a copy of that page as in the shadow space and then apply my update and then when I go and commit I just make sure I automically
21:11 install all those new pages into the into the database system and as I said this is what IBM first implemented in the 1970s uh then they realized it was actually a bad idea for performance reasons you basically have a bunch of you have to run def fragmentation on your on your um on your pages because now all the updates now end up having holes in your space you got to reuse and made squential scans really bad few systems actually do this uh Ki B and l&v are probably the two ones that are the most famous I think Ki B is still doing this I might be wrong Tokyo cabinet was a key Value Store out of Japan uh but I think that's been replaced by Kyoto cabinet it's much faster and I don't think that AES Shadow paging so again I I need to explain this to say hey this thing exists but of course I got to say don't do this all right you always almost
21:58 always want to use the logging approach either with Heap with the rad log or through log structure mer trees which we we've already covered okay so one advantage you'll get though from Shadow paging over the logging approach is that recovery like after a crash is instantaneous because again all you have to do is come back and then you immediately have this consistent or this correct state of the database CU you any changes you made from any transaction that was running while the system crash
22:29 made a bunch of dirty you know modified some dirty pages on the side and you just ignore them when you come back so if you care about recovering really really fast uh then you want to use this right ahead logging is take some time you got to replay the log and depending how fast your disc is or how often you take checkpoints which we'll cover later on
22:48 uh it might be okay but if you didn't need to have instant recovery could you expect to crash all the time you want this another system I don't know the name of it that did this back in the 197 was uh it is in the news uh but from Puerto Rico so the Puerto Rican Power Company built their own specialized database system that did Shadow paging because in the 1970s they would have power outages all the time and so if you're having multiple power outages throughout the day and your databas is going to crash when it comes back up you won't your D to be able to recover right away not to wait hours you know every single time so they they did something like
23:22 this right because they they knew they're dealing that with that environment again we'll cover we'll contrast the the shadow paging and rad logging and we'll have a whole class on RAD logging uh in a few weeks all right so the next next one in asset is consistency and as I said this is kind of a fuzzy thing that says like if if the transactions correct and the the DAV is correct or consistent then when I transaction runs it should be correct and the application has to then tell the DAV system what they means to be correct and you do this through Integrity constraints right you can add
23:58 uh check commands when in your when you create table statements or you can add constraints after the fact like if nobody's age can be negative uh then you you add those Integrity constraints and the D will guarantee that no transaction chares are run to insert someone with a negative age because it'll violate that constraint which put the database in in consistant incorrect State and it and rejects the
24:18 transaction right so basically the DAT syst is going to guarantee that all the Integrity constraints will be are true or satisfied before a transaction runs and then after a transaction runs and typically it's done on a per query basis like you can defer your your consistency checks to the very end like you you say I'll let anybody do anything and then only when I go ahead and commit then I check to see whether I violate things because maybe you could batch things up but as far as I know most systems will soon as you do a query to update something they'll check the
24:49 craint you may have heard of the term eventual consistency especially in the context of distributed systems or uh no SQL systems again we'll cover this later on but it's basically I said before like if I have now my database uh copied across multiple machines if I have strong consistency then when I when my transaction updates the database on one one node and I go commit and the datas told me yeah your data is committed then immediately if I try to read that record on another node I'll see that my update
25:18 reflected eventual consistency says that eventually your updates will get propagated so I could do my update on this one node commit and then I read that try to read that record on another node and the update hasn't arrived yet
25:31 uh so I may see an older version or I may see multiple versions depending on how how it's actually Implement if you're using Vector clocks or not so again this is this makes consistency makes more sense on distributive context uh but like you know we'll cover this in way more detail in near the end of semester on lecture 23 right we we we'll talk about how to use P or raft or two base commit to guarantee strong consistency instead of vual consistency
26:01 okay all right so now again as I said isolation is the big one we want to spend most of our time talking about so what we want to have is our database system provide this abstraction where transactions can run and the the application doesn't have to worry about is it going to see funky or weird data that it doesn't expect to see from other transactions running at the same time so you want to provide the illusion
26:27 that that any action that's running has dedicated access to the database system and it's running by itself without any other transaction at the same time but as we said in the beginning of the class we won't allow transactions run at the same time because we'll get better
26:41 parallelism right so a way we're going to achieve this concurrency is by interleaving the reads and rights on the database database objects that we talked about before in transactions but then we still want to have the database State end up to be as if we executed the transactions
26:58 one by one or or in a single file so the concurrence to a protocol that that we would Implement our database system you ever heard of two-phase locking or OCC or optimistic control that that's what these are it's going to be a an algorithm or or implementation in our system that's essentially going to be like the traffic cop in our database system that gets to decide what transaction gets overrun at what time uh and in what order and for their individual operation
27:28 what are they allowed to read and write to right and and it's going to come up sort of dynamically generate the schedule to say okay here's the things that you're allowed here's the order I'm going to execute things to again to try to avoid the problem of transactions or the the database ending up in the state that would not have occurred if I if I didn't execute them in serial
27:50 order so again we'll spend a all the next week talking about these two protocols uh so the first one would be pessimistic uh concurr toll and this basically saying before a transaction allowed to do something I'll check to see whether it's an okay thing to do and I'll block you if it's not or I'll abort you if you can't do that so you're trying to avoid problems before they occur optimistic currency control protocols would be I assume that I'm not going to have any problems so I'll let just do people do whatever they want the transactions do whatever they want I'll keep track of what they do what they read and write and then when they go to commit then I'll check to see whether
28:23 you know allowing them to run was the right thing to do or not so Monday's class next week will be on pessim protocols and then Wednesday's class next week will be on optimistic ones right and then most systems you implement just one or the
28:38 other all right so let's look at an example here why this matters so assum we have uh two accounts A and B each have $1,000 Dollar in them so the transaction we want to run uh we want to two run two two transactions the first transaction wants to transfer $100 so take $100 at a A's account and put a $100 in B's account right I'm showing sort of simple procedural logic here and then transaction two wants to compute 6%
29:03 interest on the bank accounts and update them so now the question is if I have these two transactions and I can inter leave them in any possible way that I want what are the possible outcomes that I could have for T1 and T2 right what were the possible outcomes of the state of the database after I run
29:25 them yes do we assume uh incrementing by 100 is atomic or not his question is do we assume that incrementing by 100 is atomic no we'll get that in a second so what am I doing here I'm reading a then writing a we're not that we got to read a that's one operation then write a it's another
29:49 operation so there's a lot of different outcomes we could have right because I mean it's not infinite right because there's only uh you know four operations per transaction but we know that if we want the state of the database to be as if we executed T1 followed by T2 or T2 followed by T1 then no matter what when we add up the uh the two bank accounts and compute the one 6% interest the final result of the total amount of money that should be in this Bank assuming it only has two accounts should be
30:23 2120 right so this is going to be a mind trip for a bit for for you but like from a database systems perspective what we're allowed to do is that no matter whether T1 is submitted first followed by T2 or t t first prob T1 we're actually allowed to order execute them in any order that we
30:43 want if you cared about making sure T1 executes first followed by T2 you either have to do this in your application code like have a queue that you that the application then send requests or there are some systems that provide a stronger level of of of cons guarantees something like if you ever heard of Google spanner right they provide external consistency like what they'll guarantee is that the order you submited is the order that things will commit but most systems don't do that most most most applications don't don't even need that
31:12 so this is going to be a a little trick that we can have that we can reorder things anybody we want but all at the end of the day all that matters is that we add up the money and put 6% uh 6% interest on it that the T final sum is 2120
31:28 so the two legal outcomes we have is we execute uh T1 first Follow by T2 or T2 followed by T1 and again it doesn't matter of what the final state is for a and b as long as again A plus b at the end of the day is
31:44 2120 so what does that look like so I would have uh if I execute these in what I call in serial order so this is an execution schedule so you see I have a begin then I have my uh my a a equals a - 100 b = b b plus plus 100 in this verse here I execute T1 first followed by T2 in the other example here I execute T2 followed by uh T1 and in both these cases even though A and B have different values again if I just add them together then I'm guaranteeing
32:17 2120 so so this is a Serial ordering right that I can execute T you know one transaction at a at a time but then now if I want to interlead them and again we talked about why we want to do this right get better parallelism if one one transaction has to block CU there's a Miss in the buffer pool right another guy can keep running
32:38 right this is all fine and dandy but now I got to be careful about when I want to inter Le things that I don't violate or I don't end up with the state of the database that would not have occurred if I if I had executed them in Ser order either T1 followed by T2 or T2 followed by
32:53 T1 so if I go back here right now T1 starts takes the money out of out of a but then for whatever reason it gets blocked right because a page you know page miss or whatever and then T2 starts running and then it computes the interest on a then there's a Contex switch back over T1 starts running again as the $100 It Go goes ahead and commits and then T2 starts running again it then adds the interest to B and it goes ahead and
33:18 commit again and this example here even though I'm inter leave the transactions it's equivalent to one where T1 executed first followed by T2 and the key thing to point out here is that we're we're making sure that any operation any update operation on T1 On A and B happens before the the operation uh another update operation on that same object in the next transaction yes um why do we Define equivalent based on the sum of A and B not the values of A and B
33:51 the a values the values for a and are different for these two right so question is why are we defining the that they're equivalent based on the with the the total sum of of this and not the actual values A and B because what I'm saying in this programming model we're allowed to order things any way that we want right so long as the the the state of the database is equivalent to
34:17 executing executing one the transactions in a Serial order and this world that's okay and that's different than maybe what you're what you're used to in like parallel programming like in like C++ or python or whatever you're using but in our world of transactions that's
34:33 okay the reason why we want to do this is because it's going to open a bunch of opportunities for additional parallelism that we would not be able to get and again at a high level this is correct but it's you know different idea of
34:49 correctness so if you look at this example here right this is example a bad inter leaving I take a $100 out of a then I context now execute T2 then I compute interest on a then I compute interest on B then I now go switch back over and add $100 back to to to B right the end State here is not equivalent to one where would execute them in a seral
35:10 ordering right because I add them add the two numbers together now I get 21 2114 and I'm missing $6 and if it was a bank you'd be pissed right if it's your money right so he was SED asking before like can I assume that these this the a equal a minus one or the b equals P plus one is that what the D actually sees no right what you're really seeing is a read on a followed by a write on a and then a read on a right read on B followed by right on B right so that's how the D syst can reason about these operations it doesn't know the high level semantics about what the operation is actually doing it just knows that you read something and then you wrote something
36:00 we'll see later on if we do know whether uh we do we we can somehow infer the semantics of what the the transactions are actually doing we can actually get even better parallelism but that's impossible and nobody actually does it but we'll see that later in this class so now the question is all right sort of you sort of easy to see from us just looking at this whether this this schedule is correct because it's only two transactions they're doing pretty simple things and I I just sort of add the numbers together but this is obviously this would not be scalable and this wouldn't actually work in a um in a full you know in a real syst there's a lot of transactions so we need a better way to figure out how to determine these These are equ uh this is okay so the goal we're trying to figure out now is can we look at a schedule and say is this going to be equivalent to a schedule that would that would that would put the datas in the State uh from a schedule that executed in in seral execution
36:53 order so this is just re implementing what of our our re uh repeating what I've already said so a seral schedule is one where we don't we don't do enter e leaving with different transactions and I'm going to say again two schedules will be equivalent if the end state of the database will be equivalent to we executing the first schedule and the second schedule assuming they start at the same database
37:15 state so the thing that that the the gold standard of the isolation level that we're going want to support is called serializable uh serializable uh isolation serializable schedules there is actually a higher level of sterilizability uh and that's that strong sterilizability strong consistency I said where you guarantee things are executed in the order that they arrive but again most systems don't give you that most people don't need it so a sterilizable schedule is g to be one where it'll it'll it'll be arbitrary interleading of operations and transactions that put the DAT in the same state as if it was in uh executed in serial
37:53 ordering so this this is a bit different than than what may used to in in in programming in other contexts right the the correctness is not going to be based on the things the time that things arrive or actually in some cases that the time that things
38:08 commit because your transaction may say commit and then the order that it gets committed is not the order that it arrived and also not not the order that it executed that's kind of funky but again because we can play around with this with these games about how we're going to order things in our database system we're going to way better parallelism than we would if we just have a single single Q execute things one after
38:35 another yes you give an example where the order of transaction doesn't he said can I give an example where the order of the transaction doesn't matter uh I mean the bank account one just gave us now doesn't matter whether T1 ex T2 F T2 versus T1 it doesn't matter it's the end state of the D is still correct because it's equivalent to executing things in a Serial order
39:00 if I if I wanted to make sure I did the transfer first followed by Computing the interest then you have to do that in your application you have to tell me execute T1 and then only when T1 comes back and says I've committed then you execute T2 the data system can't do that for you
39:14 though spanner can but most systems don't do that all right so now we got we need a way to formulate Define okay how do we know whether two schedules equivalent right and we kind of intuitively saw that what had to do of the The Ordering of the operations of when we read and wrote objects to the same object across different
39:37 transactions so we're going to Define this as conflicts between transactions in a schedule if they do some kind of operation on the same object either one uh either one does a read and a write or one does a write and a read and they're from different transactions running at the same time and they're they're touching the same object or
39:58 objects right so that'll be the notion of a conflict to say that these things can't can't be equivalent we can't we can't inter or leave them and then there's going to be now different anomalies that can occur based on the con type of conflicts we can have in our schedules so you can have a read WR a right read and a right right conflict why no read read conflict it's fine because if you read the same thing and I read the same thing not a conflict right so I'm going to go through these three examples in more detail I'll just also say there's two other types of conflicts that we're not going to talk about today called Phantom
40:30 reads uh and WR skew so we'll talk about Phantom reads next class it's basically if I scan some data I don't see something someone's insert something in between that that range and I scan it again and now I see it but now we you talking about aggregations right and not not simple re operations so we'll see that next class how to fix that uh and then right SCH we'll see uh in two weeks we'll talk about multivers control it's basically I read the Davis at the same time everything looks okay and we end up writing things and it it's not into the serial ordering that does not make any sense you'll see this later on right
41:02 again we we'll cover this in lecture 17 19 but today's class I I want to focus on on the basic three all right the first one is on repeatable reads these are read write conflicts and this is where a transaction will get different values reading the same object multiple times
41:19 while it's running so T1 starts reads a it's a gets back $10 then there's a context which T2 starts running it reads A gets $10 and then there's some logic that says if my account has $10 give it $5 make it 15 and then now it writes it back into the database and go ahead and commit now when T1 runs again instead of seeing $10 it sees
41:43 $19 right and again if I was executing in serial order T1 Follow by T2 if I read a twice I should get $10 but because I interleaved the second transaction was allowed to make that update now I'm getting what again what is called unrepeatable read I'm I'm reading the same thing and not getting back the value that I saw before which should not occur if I was executing them in again in Sero
42:06 ordering so this is a problem we we want to make sure we avoid this yes transaction question is what if he removed on the commit on the second transaction like so basically if I put this down here again this depends on on the implementation of the datab system which we're not talking about just yet
42:24 you would have to make sure that this thing that this this right is is either can't occur because this guy holds a lock for it or this right occurs in a private workspace that that this guy can't see and you hide it from him so the Locking will be next class the hide it from you will be Wednesday's class next week but I'm trying to deal with the intuition and not actual implementation but you can kind of see how we can start doing these things and to protect
42:52 ourselves because then we have to worry about Deadlocks too if we start about locking again we'll cover that all right the next anomaly is a right read conflict also called a dirty read and this is where a transaction is allowed to read something from uh a transaction that hasn't committed yet so we read a get $10 write back $12 this guy then reads uh a sees $12 which again it should not have saw if uh if they were running in true serial ordering
43:21 right and then it writes back whatever $4 whatever value you want but then now later on T1 AB reports or rolls back so that means we got to undo the change we made in in on a but wait a minute tach you Reddit and already committed and we told the outside world yep we got your change but you again the logic could have been if my bank account has $12 make it $14 and that would have not occurred if the again if you were running in serial ordering so this is the problem we can't allow
43:53 this all right and the last one would be the right right conflicts or loss updates and this is where when we have a one transaction overwrites an update made by another transaction that shouldn't have occurred so again T1 starts right on a T2 then starts writes $19 and then for B they put in Bob and then when this comes back over now does a write on B and puts an
44:16 ALICE right this should not occur because it either should be $10 Alice or $19 and Bob but in this schedule here we have $19 and Alice which again would not could not occur if there were if there was running into a true serial
44:34 ordering does that make sense all right so now we know how we know how to identify the conflicts uh but how do we know again for any arbitrary in or leaving how do we know whether it's actually equivalent to uh serial ordering how do we know our schedule is actually serializable as we we would
44:59 say so to do this we're going to go ahead and check this whether our schedules are are correct looking at the conflix uh in in today's class this is just understanding the the again the theory behind it to understand what correctness actually means in a in a real system you would actually not have going back here you would not have the schedule ahead of time in most systems
45:21 right because think how this would work in your application you call begin you write you send a query get some data back goes back to your application then use some do some more logic and then do another query right so the DAT system doesn't see here's all my reads and writes ahead of time it says see it's one read one right back and forth so things are coming in uh incrementally
45:38 and you you wouldn't be able to maybe figure this out so the protocol is next week how do I do this in in a dynamic environment to keep make sure that you don't you know you don't violate these you don't hit these anomalies today's class is really saying okay if I look at a schedule if I know all the the operations ahead of time how do I know whether it's it's correct or
45:55 not so now this gets this also going to be a little bit weird because now we're talk about two different levels of serializability there's actually more uh it's in the theory uh Theory world we don't care about that um but there be the notion of conflict serializability and view serializability in most database systems if they support serializable transactions some systems will lie to you Oracle does this uh some systems they if they support serializable transactions you'll get in Conflict
46:21 serializability view seriz is a uh no system can do this because you have to understand what the application actually wants but i' like to present it to you guys in class because again it's a different way to think about correctness and show that there's opportunities to get even better parallelism you could get using two-phase locking and and mvcc and OC we'll talk about next week but to do that you got to know what the application means when it says do something for me which is you know is is very difficult to do so again most systems when you say I want see a lot of transactions you're getting conflict liability again an oracle if you say I want see lot of transaction they say yep no problem but it's really a lower isolation level it's been that way since since the '90s
46:57 and they don't care again most people may not care all right so we're going to say now on conflict cability that that two schedules be conflict equivalent if and only if they are uh they're they're mul transactions touching the same same objects and then the The Ordering of the conflicting actions like a like a read write right right on the same thing that they're going to be ordered in in the same way so then we can say a given schedule conflex serializable if it's equivalent to some serial
47:30 ordering all right well this is kind of vague what do you know this what does it actually mean I'm being kind of hand we here how can we actually determine this so to do this uh a really simple algorith is to generate what's called a dependency
47:42 graph so the idea here is that we would have in our graph uh a node for every single transaction that's running in our schedule and then we would connect an edge between them if the one transaction is is doing an operation on some object that conflicts with the other transaction and then that operation appears in in the schedule before the other conflicting operation from the other
48:08 transaction so in Wikipedia or the textbook they might call this dependency graph but the the idea is the same so now to determine whether our schedule is conflict serializable so equivalent to a a Serial ordering that as long as our dependency graph doesn't have any Cycles
48:24 then we know that we we we're not going to have any conflicts or have any issues or any the anomalies I talked about before so let's look look at this example here so i T1 followed by T2 T1 writes on a reads on a and then writes on reads on B and writes on B and then T2 is going to do the exact same thing so we just sort of go down one by one and for every single operation look across to see do we have any any conflicting operations again we're one
48:49 uh it's either ra Follow by right or right on a right and then the operation T1 or the one transaction occurs before the other one the conflicting operation in the other transaction so in this case here we do a write on a followed by a read on a right that's a conflict so we would have an edge from T1 to T2 on a we have a read on a on T1 but then we do a write on uh a on T2 but the read occurs before the right so there's not there's not an edge going the other direction at least at least on
49:18 a but then now we have this right on B in T2 occurs before the right on sorry the right on B occurs before the read on B uh in T1 so then now we have an edge between T2 and T1 here on B and then now we know we have a cycle under dependency graph and therefore this schedule will not be uh it's not equivalent to a uh serial
49:39 ordering right all right and the Hyo intuition is that the the output of T1 depends on some T2 doing something and the output of T2 depends on T1 doing something and therefore we know that this could not occur if they were executing in serial ordering
49:58 all right for two transactions that's pretty easy let's see how to do this in now three transactions so again so first we start off with the read on a occurs before the the right on a uh so that's a pro so that's we have an edge there then we have now the right on a occurs for the read on a there so we have Edge uh that's another overlapping Edge the right on a before in T1 occurs before the right on a and T3 now we have other Edge on there but that's a repeat we do a write on B and T2 follow read on B T
50:27 T1 so the edge going there right and then we have the right on B Follow by right on B that's not a conflict right so there's no Edge there and then we're done so is this equivalent to a Sero ordering Ser execution ordering yes because there's no cycle right so it's equivalent to T2 Follow by T1 followed by T3 right you think start of think about it like all I care about is like you know what's what's in my n State I had the right on B that's good there uh sorry the right on B from here
50:57 uh or sorry the t2 executes first right so that happens here then T1 executes that's there and then T T1 ex T3 then executes right so T2 Follow by T1 Follow by T3 again so in this case here remember I said even though uh the transactions may have started at different times I'm going to commit them in the order that the guarantees that the things are
51:21 sterilizable so T3 is going to go run after T2 even though the begin command started before t2s begin command and that's okay so let's look at another example so again now we're going back to doing more uh the more complex operations so now we have we intermix with the the object code s the procedural code but we still have the read on a follow by the write on a but now we see like a equals a minus 10 like that's going to happen outside the database Sy that's like we take a local variable and make a change
51:55 all right and then now in our T2 transaction all we're doing is Computing an aggregation like the sum of all the of the values uh for the accounts in A and B and then there isn't a command the print in SQL uh like this just Echo means I'm I'm going to spit out the whatever the final result of the sum is
52:12 right think of returning the value of the sum all right so now if we do our analysis again we have a conflict between on T1 T2 on the right on a and read on a so we have an edge there but then we also have a write on a and then uh
52:27 uh what is this right on a I don't know why there's two edges there ignore that uh the read on B follow read on here here and now that's going back now we have a cycle right so this example here would not be equivalent to a Serial ordering under under the definition of conflict St
52:44 realizable right because we have the cycle independency graph yes what happens one of the transactions question is what happens if another transaction one of the transactions aborts so say this guy aborts here uh under this schedule what would happen is you would read the right from the this guy T2 would read the right or a and it shouldn't have read it so therefore it because even though it aborted I still have that cycle and I have I have to roll back both of them
53:14 like in the simplest uh situation like if T1 reads A twice and only reads A and T2 modifies a and then I don't see how this dependency gra would reflect this kind of situation you're if if T1 reads A twice yes uh say reads A and then T2 writes a yes and then T T1 reads A again and T2 aborts T2 aborts roll back and then T1 ALS reads it again so let's not get into like if you call aort how like what did that rollback actually look like just take it like
53:56 in your example yes like if if I called aort and I roll back the change from T2 and then T1 reads it again and it would see it would see the previous value you're correct that would be that's okay and it wouldn't get picked up in the dependency
54:10 graph assume that for all just ignore whether aborts are going to roll back or not just take it for the what what are the operations that I'm doing and then I fill my dependency graph based on that yes why is there a dependency from wa to RV th this this is a mistake ignore that yeah get rid of that edge
54:30 I'll fix that later all right so yes why is reading before writing a problem why is reading before writing a problem uh because if this thing this thing should have um if this was running in true Ser ordering then then this thing should have read read this update and it didn't right so it read the first update there's an edge there and then it doesn't read the next update so it should either read both updates or none of the updates and I've read half of them and that's bad that's
55:11 wrong all right so is there a way we can modify or change this what this application code is doing to still be correct even though it's not conflix orable even though we're still going to have a dependency graph well what if instead of uh instead of just adding the sum together and printing out what if I just go check to see whether the the value inside of it is greater than zero greater than equal to zero and then I just increment the
55:37 sum or the count of the number of counts that are greater than zero so the logic has changed like the previous one was was Computing the the aggregate sum this is now saying give me the count of the number of counts that have more than more than uh zero assuming all the counts are with you know have more than zero that even under this ordering this with this inner leaving this count would always still be the
56:00 same right ass all the values all all the values have enough that they take $10 out and it doesn't cause any problems and the count is still going to be still going to be the same even though I this is not conflict serializable if my logic looks like this then it's actually is equivalent to a s to a Serial ordering even though it's not uh even though I'm inter
56:23 leaving so this is what view sterilizability is so it's a more broader definition of sterilizability where if if you understand the semantics of what the application actually wants to do then you actually can inter leave things that you would not be able to do under conflict
56:39 realizability right so there's a former definition here that we don't need to go to right about view clency it's just saying that again if you if the final value of of that comes out of the transactions is equivalent to one where of of a of a serial ordering
56:56 even if the the operations actually should not have occurred because they conflict then that's okay so might maybe this example is a bit difficult to understand but let's look at a really a much more simple one so I have three transactions T1 does a read on a write on a T2 does a write on a and T3 does a write on a so these are called Blind rights in in transactions so if I just write to something without actually ever reading it first it's a it's called it's called a blind right right because you're you're updating something without actually looking at it
57:28 first so again if I now build my dependency graph I would have a conflict on T1 Follow by T2 uh and then T1 Follow by T3 going back to T2 to T1 and then from uh T2 to T3 as well right because again they're they're they're reading they're writing things that shouldn't be allowed to write and then additional one between t T2 and
57:52 T3 but if I look at this schedule the only thing I care about is what's the final value of of a and in this example here it all all it matters is whatever T T3 wrote to it who cares whether T1 read something and wrote something and whether T2 wrote something as well I'm basically don't you know the Nate of the database is just whatever this last guy wrote is what what survives and that's the only thing I care
58:22 about so this would be equivalent or view equivalent to a schedule where T1 executes first followed by T2 followed by T3 right because again the only thing I care about is who who last wrote to T3 so view equivalency is going to allow for all schedules that are conflict sterilizable as well as additional view sterilizable schedules in particular the ones that do blind
58:50 rights because you you just don't care so I mean this is defining is more more formulate just trying to say again like that there's if you can support view sterilizability that you can do you get more better parallelism because you can understand what the application actually wants or the meaning of the transactions themselves at a higher level but that requires you to basically do some kind of static analysis or talk to a human which is the worst thing to do to say is this actually okay or not and so that's why no system actually supports this yes s can L um so if someone reads T1 commit
59:27 uh but before T2 begin we actually read the commit value by T1 but for the first schedule it doesn't work like that so does that not break U the equivalent see your question is if there's another transaction that reads reads what t1s a or T2 is a yeah if um it reads A after so for the actualizable schedule if it reads after T1 commits but before T2 begin it will read whatever the T1 writes correct but for the schedule on if we read it like at the approximate same uh position it's actually not going to read the value that T1 writes so does that break uh equivalency or no uh for for serial for
1:00:10 conflict seizable or VI serializable so question is if I have another transaction that say that does a read in between T1 and T2 does it write anything no then uh let's see how would that work so if you're so it' be basically reading right here um before the before like reading here yeah somewhere
1:00:34 uh that if it just reads that would be okay because it would see it would see the update by T2 so it's not equalent no you would have it you would have it be uh you would have it be say this is T4 You'have T1 T2 T4 then sees the right on on T from T2 and then T3
1:00:57 commits that's okay but that that would have that would certainly have conflicts in that case because it's just a read uh and there it doesn't do anything else after that it it actually wouldn't introduce a a a cycle in the dependency graph um but just going back here like
1:01:15 the this thing has like without that additional thing you have you already have a cycle so it doesn't matter that you you wouldn't this would not be a complex liable schedule but yes you could introduce a read like that that it would it would it would
1:01:30 work all right so a better way to think about all this sort of isolation levels in scheduling stuff is you can this this space here is all possible schedules you could have for any possible ordering of of transactions they're doing anything in your database and then a small subset of this is going to be the serial
1:01:48 orderings but then around that would be the conflict Ser liall schedules which includes you know which is a superet of the ser ordering and around that is the view sterilizable ones and like I said there's additional ones after uh that go around the vizable ones but we don't we don't care about care about
1:02:07 those and we'll see next class when we start talking about like cascading aborts things there'll be some schedules that will be another category schedules that will Encompass view stability conflict sterilizability and serial scheduling but also some some non ciz
1:02:22 schedules so in most systems again when you call ciz you're going to get this this boundary here and we'll see next class how do we actually enforce that all right to finish up real quickly I talk about transaction durability uh again we're going to have a whole lecture on RAD logging and and checkpoints and Recovery uh so there's not much to say here but it's basically the things I said at the beginning of the class is that we need to make sure that if a transaction commits and we tell the outside world the data system tells the outside world that your transaction has successfully committed
1:02:53 then if there is a crash then no matter what happens if they come back they should still be able to see their changes right you can have even stricter levels of durability meaning if I if I crash and then the machine catches on fire or the data center burns down then if I have really strong durability guarantees I still see my data how well you have to have backups on on you know another data center another
1:03:18 machines right again we we'll cover how we'll see how we handle that later on but the basic idea is going to be the logging and the and the shadow paging and we'll see how to make these run fast uh in a few
1:03:30 weeks again so going back to our our asset acronyms of all these different properties right you can think of like the atomicity and the durability are we relying on the redoing undo mechanisms in our dat system so like the the the right head log will give us redo the shadow paging stuff will give us undo
1:03:47 right head log gives us undo as well the consistency models be guaranteed by the Integrity constraints and additional consensus protocols like paos and raft that we'll see later on and then the isolation stuff will be handled by the concurrent sh protocols like two phase locking and OC that we'll see starting next week
1:04:08 okay all right so again hopefully this again just a quick crash course brain dump of like here's the high level of things we're going to start talking about now when we talk about transactions what does it mean to be correct what does it mean to have serializable uh seriz while isolation um and again this is another good example of why you don't want to in your app code you don't want to write a bunch of database like stuff yourself because
1:04:30 this is really hard to do it's really hard to get correct and you want to rely on an existing data system that already has a battle hardened concurrency show protocol and Recovery methods or protocols implemented and not you winging it like use an map or something stupid like that
1:04:44 right and so there was a phase about 10 years ago during the nosql mov if you ever heard that term where all these guys are like hey transactions are a bad idea they're slow we don't want to do them
1:04:56 who is the big people who was can can I name the one company that was probably the most the biggest proponent of this came before Google well that came from Google yeah but level DB was a single node uh stor manager but Google built this system called Big Table uh right which is still around and they were like oh we don't need transactions on this it'll run faster it' be more web scale and so forth um and but then Google wrote a paper uh a paper on spanner you know very famous transaction system uh about 10 years ago and there's this little blurb in here that says uh it's we believe it's better to have application programmers deal with performance problems due to overuse of transactions
1:05:37 and then have have you know how to make those things run fast rather than everyone writing a bunch of code to deal with the lack of transactions so basically saying instead of having your Rando JavaScript programmers have to figure out how to deal with inconsistent data or incorrect data because your system doesn't run transactions you're better off getting people like Jeff Dean give them a lot of money really make really get really smart people in a single room to make the transactions run fast as possible and deal with the people uh you know deal with people's
1:06:02 performance issues that come up right because that's going to be way more way more productive for the company for the organization if you have the system support transactions because you don't have the right additional repeated logic over and over again to deal with bad
1:06:16 data right so all the no SQL systems he mentioned Cassandra uh CB there was a bunch of systems I C does just for transactions but all the systems that made a big deal about oh we don't support transactions look how web scale we are guess what 10 years later they all added transactions right because this these concepts are super important and it's it's a it's from a programmer's perspective it's way easier to deal with
1:06:42 uh if you can assume the datas is running your transaction are running in seral ordering all right so next class uh we'll talk about two-phase locking which is a pessimistic commertial protocol that we we use to to provide or guarantee the ordering the serializable ordering of transactions and those are isolation levels which will be the sort of dirty Secret in all this where I made a big deal about how important serializability is and then we talking about protocols to to to guarantee it
1:07:10 what turns out most systems don't actually even support this or even give it to you by default by default they're going to give you a lower isolation level where some of those anomalies I talked about could actually occur and does it
1:07:22 matter nobody knows right so we'll cover that next class uh and and see we'll open up postgress and see see what it does okay any last questions before we F to fireable yes is it necessary for like olap system to have transaction his question is uh do olap systems often have transactional features yes why is it for question why for like bulk updates right uh often times people want to like you you you upload a bunch of data uh and then now you have maybe Corrections for it and make sure that happens automically are there system that does not really
1:08:01 support question are there systems that don't support any transactions uh I mean yeah there's tons of them right uh like from Olaf and OTP operational side absolutely yes um trying to think probably the most famous one that doesn't
1:08:16 um I think CB might support them now um even Dynam from Amazon that for a big time longest time they were like we don't we're not doing transactions they now have transactions uh what they do is slightly different where they so I may said like most systems don't see the schedule ahead of time in Dynamo DB you sort of run your your transaction first it doesn't actually update anything it just watches what you do gets all the reads and gets your reads and write operations
1:08:41 and then submits that to the databas system and then now can actually figure out the schedule of things um font DB is another system that does that but most systems don't don't work that way but yeah there's trying to think any off hand uh but like pretty much all the major oap systems they'll ALS sport transactions uh any the key value stores uh and now most of them support transactions but you can you can build larger transactions around them and we'll cover that later
1:09:08 on okay so let's see if the Firebolt guy is here okay I I wish you didn't say
2. Jump to
1:09:13 it's Fork of Click house the best way to describe us wait what you say I said I wish you didn't say didn't characterize Firebolt as Fork of C house this is just like I don't know 10% of what Firebolt is but it's okay it was so it was originally a fork though right like uh because I remember when when the web page came public a few years ago I was like they do this this this this this I'm like how the hell did a brand new startup have all these amazing
1:09:42 features uh and like they've only been around for two months I mean you guys have Rewritten a lot of stuff I'm not trying to belit the work I'm just saying that like the the provance is all right sorry go for it your time some subsystems for f cck house others for fork of other systems but doesn't matter anyway so my name is Mos tansi and I represent far by the way um can you switch to the slides I think I'm
1:10:07 sharing oh you see okay just I don't see it okay all go so um let me start my timer so I represent Firebolt here and we thought for this presentation we will go and um talk about something related to the stuff you guys learned recently last week and this week unfortunately I thought this week you're going to learn about query planner uh otherwise would have talked about transaction manager on Firebolt which I think is very interesting but hey maybe next year so
1:10:43 um rather than going into breath and talking about architecture and so on without we'll spend a little bit more time on one of the aspects of Firebolt and hopefully you can connect it with the stuff that you will already
1:10:55 so even though I'm presenting this uh this is a joint work of many others in Fireball so they should get that credit uh before we go into the subject itself let me set up a context and talk about what Firebolt is and what is it for so our slogan is it's cloud data warehouse for data intensive applications which sounds like some kind of marketing slogan so let me break it down for you first of all it's data warehouse so it has typical data Warehouse features like colum storage vectorized execution uh post compatible SQL dialect um obviously you know
1:11:35 transactions we use uh optimistic concurrency control on VCC and snapshot isolation as a default isolation level and so on it is also run in the cloud so it has all the typical Cloud features like two separation of storage and compute um multi architecture where any note in any cluster can update any data
1:11:58 if it has permissions of course um since we're talking about analytical data volumes it's distributed execution engine uh so all the typical stuff so the more interesting aspect is the second one for data intensive applications and what we mean by data intensive applications like user facing applications that you will run um in the browser or uh in mobile device some something that um you know can have low latency and by low latency I mean tens of milliseconds our fastest nontrivial
1:12:32 production quer is 5 milliseconds and high concurrency and by high concurrency I mean thousands of QPS and again this is typically like even a single note my SQL can handle it uh on relatively small data volume but we're talking about analytics so we're talking about tens of
1:12:53 terabytes um we have customer who Beyond petabyte scale and like daare houses today are very capable can do many things but Ser user facing applications is something that they cannot do and this is what Firebolt is trying to do and we kind of joke that you know we want to be faster than blink of an ey and here's a grave to prove that we really are um although we using comedian latency which is a little bit of cheating but hopefully the point got across so how how we able to do it like it's not like we have some magic
1:13:28 want uh so it's hard to to achieve all those properties but there are few things which are working in our favor and most importantly if we're talking about supporting of applications there are few things which are fixed the workload is fixed it's predictable there are tens or maybe hundreds of query patterns but it's not like you see completely different query pattern every time or you know schema changes and frequent usually
1:13:56 um if for cl or schema changes it means new version of application get deployed um we also deal with read mostler queries we do support updates and again that's why transactions are important it could be B inserts it could be also Point gml updates and deletes that's fine uh but their volume is not that big and usually happen on fact tables and not on Dimension ones so um
1:14:25 since we have those things that're helping us to to achieve this low latency and high concurrency scale and there are few techniques uh some are classic ones like indexing which is well known uh just you know you over clo you build indexes for it others I thought you will talk about cost based Optimizer today so just wanted to say uh like the biggest problem of cost based optimizers is cardinality estimates and how they're propagated so we use history based optimizations in instead so rather than trying to guess all the cardinalities we just look at query history at every stage what actually happened and feed it back to the
1:15:04 planner but today uh so there are quite a few of those today we're going to talk about sub result cash and Country use so let me break this um into its component first of all cash and Country use what what is it so as we mentioned uh our workloads are very predictable uh you know they very part are very stable doesn't mean we're seeing the same queres all the time uh but the same pattern so most of the queries stays the same some element of it changes maybe
1:15:35 filter condition maybe something else but the rest of the query stays the same again do analytical system the queries are kind of complex they can have many joints and window functions and whatnot um so obviously if you have something which repeats over and over again cashing is an obvious solution to go to and cing of course is uous in software in general in databases in particular
1:16:00 and um there are different forms of it buffer pool you can think about it as caching at the scan operator level at the bottom of the query plan and then many system do full result caching which you can think about caching at the top of the plan but of course you know one may wonder why not to cash anywh else in the plan and this is what we mean by sub result caching and re
1:16:25 and it even though this has been researched like first papers about it showed up in 80s and there are more recent ones that we put here it's surprisingly rare in real systems uh to do it but Fireball does it and that's what we're going to talk about so um that was question what do we mean by sub result so to explain this uh let's pick this madeup example of query on top of tpch schema there are couple of joints here three t to joins one aggregation
1:16:56 let's take a look at how query plan of it looks like this is the query plan exactly what I just said three scans to joins one aggregation by sub results we mean two things one is output of any operator uh can be cached and you know if it's on the top of the plan It's the final result if it's in the middle it's sub result okay Prett is straightforward but also some artifacts of The Operators not the final result for example hash join
1:17:26 builds the hash table that it's going to prob into to so it's a perfect Target for the cashing like it's not final result but we still call it sub result caching okay um well how it works in PR like a little bit more details so we rely on planner to insert what we call maybe cach operator which tells us what are the good points in the plan to do caching it's called maybe cash because runtime doesn't have to produce cash it it looks at some constraints like it doesn't want to to add crashes which are too big or valate some other settings
1:18:02 that we have that's why it's maybe um the interesting thing that um with vectorizer time it's relatively cheap to do those caches because Vector R time works by passing blocks between the operators so caching c means just don't throw this block away after you're done with it store it somewhere so it's cheap to do this still take memory of course
1:18:26 um um but that's why it really works well um in this setup so let's take a look at uh how this work in example of our query so the same query plan here planner decided to put maybe cach operator at the top of the plan so it's full result caching and also both join are going to store their hash table so we run the square it has to execute everything and there are three things stored in fire cach when we this Square second time of course the might be cash is on the top and we already have results for it so we had to do nothing okay so this like full result cach kind of trivial straightforward
1:19:07 let's make it a little bit more interesting so now query changed so we added filter to it see a filter on the order stable um which is the biggest table here and now plan looks different we pushed filter all the way down to the scan of orders so we can no longer reuse the cach for the entire quer because it's different um and left side changed but the right side didn't change right it's this filter doesn't affect nation and customer Dimension tables so we don't execute the entire right sub three and we don't rebuild a hash table for the second joint so this query is still
1:19:45 much much faster I think it's like five times faster on execution another example so which can change query in other ways let's say we wanted to compute average and for whatever reason we said some divide by count instead of a or maybe planner decided to write it like that so in this case it's different quer but now planner notices well there is kind of um it's slow cardinality like the you know there are only in the result we'll only have few rows because nation is a small table
1:20:21 and this final projection to do division actually keeps the Cardinal so maybe it's better to put maybe cash below it and it's indeed was smart decision because all the plan below it is exactly the same as we saw before so this sare will also work very fast even though it's not identical to the original one right so this is basically the idea um few other things um obviously like with any other cash we need to think about cash eviction and the most obvious commonly used policy L you turns out is not the best one the best one is to look at cost benefit that's was described in the papers we tried out different ones and paper was right uh so basically you say how much benefit you get from it and you estimate it by looking how much time you spend executing the sub Tre and how much it costs you like how big the cash how much memory are spending on it and
1:21:17 you take both of those into account and in our experiments in real production we saw that can be up to twice as more effective as simple lru okay how does it actually work in real production with real customers so we get in general we get 10x saving
1:21:38 usually sometimes even more and 10x sounds like a good number but we actually think we can make it much much better because right now our planner is too conservative with putting maybe cash so I think we can like some calculation show we can go to 100 XX so maybe even higher
1:21:56 uh and here we can see it's uneven some customers en join more than 95% of saving and some injury less and we need to work on them so um this is what we have there are still plenty of open problems uh where exactly to put this med cach operator this is uh we talked about that we use history based Optimizer so obvious solution is to go look at the history find common sub plants put Maybe Cas there this becomes multi
1:22:26 optimization problem um we're experimenting with it it also requires our planner to do some scary nonintuitive things like pushing down predicate is such a common rule but it may destroy caches if it goes too too deep like if it went to the our right sub three in our example so sometimes maybe planner should pull up predicates instead which does sound scary but can have great benefits also Al the way we design our data structures even though
1:22:59 we aim to be fastest we don't design them for Speed we design them for uh for size we say okay if I can design hash table it's not the fastest hash table but it takes 10 times less memory and actually build uh something like that uh it will still be not benefit to our system uh because we'll be able to fit 10 times more of those cash tables and uh sa more qu from the cash and so on so
1:23:27 and by the way if those problems and many others sound interesting to you here's a link to our open positions and this is the end of 10 minutes okay uh any questions for mosa yes is in the case where everything is Cash do you have any statistics on like what percent ofu is used and what's not all so this question is uh in the case do you have any statistics you keep track of like what percentage of the items in the cash are used versus not
1:24:02 used well so we right now constrain the amount this cash can take because there are other things which are like especially in execution I think we're going spending about 20% of our r on those CES still I that's a b cash right these boxes running with a lot lot of ram yeah another question yes determine what sub results of what operators are cashed the question is how do you determine what sub result of what operators are
1:24:32 cached so it's a little bit of urtical now so the way we go about it uh all the hash tables are cach and we also put maybe cash at the top of the plan and see how much down we can push it as long as it goes to cardinality preserving operators so as I hinted it's not as aggressive as it could be
1:24:55 probably can do better yes all right so yeah so I I want to not back check what I said but like yes Fireball started off to click for a click house but as you talked about here they've Rewritten everything uh as far as I can tell over the last couple years uh and so click house doesn't do this caching stuff that they're doing and one of the reasons why they can do all this cool stuff is because it's a cloud system you see all the queries so you can you can see what the workload look likees across all your customers you identify what are the ways to to optimize them
1:25:25 uh and then you know this caching stuff is is a big part of it um and again it's awesome the think about like we took what we talked about last class like here here's how to build a query plan and she showed basically that query plan looks like everything we talked about before now you inject this caching piece that doesn't change anything about the query plan itself but now you you're reading stuff from from the cache and the query produces the same result this is why relational model and Y SQ is an aome idea because you can do all these tricks and the the application doesn't change any of their stuff because it just gets all the benefit of this cashing stuff for free I mean free and quotes they're paying that but you know what I mean right they don't you don't have to change any of your application code to get all these benefits and this is why SQL is is a is a in racial model is a brilliant idea um and that's why people pay a lot of money for this okay all right let's give mosha round
1:26:12 Applause okay homework four is Du Sunday and I'll see everyone on on Monday okay motion thank you so much that was awesome I need something refreshing when I get finished manifesting too cold a whole B like Smith and Wesson one court and my th's hip hop related write a rhyme and my pants intoxicated lyrics are quicker with a simple Mo lier since I'm a city slicker play Waves a picker rhes I create rotate out aate to quick to duplicate F re at escate mik's at Fahrenheit when I hold it real CH then I'm in flight then we ignite BL starts to boil I heat up the party for you let my girl R me and my mic down with oil Rec still turn with third Dee Bur learning from one man I heat up your brain give it a suntan so just cool let the temperature rise to cool it all with same odds
1:27:05 [Music]