CMU Database Group · 1:27:07 · https://www.youtube.com/watch?v=niLwbfE3V9Q
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 pistol to put the V around the issue never miss coming that's offici
0:30 I want to cover today plus I want to spend time at the end hopefully giving popping up my seq postgress and throwing real transactions at it so you guys can see that like oh and's not making up the stuff is exact how it works uh when we expect what the davidon does when we run transactions so quickly um the ministrative stuff project 3 is due this Sunday on the 17th at at midnight again project four will released on uh this week I think on Wednesday or tomorrow um the final exam will be Friday December 13th at 8:30 a.m.
0:56 I forget where but I'll announce that uh again there will not be an early exam I don't care if your your your your aunt Uncle's 50th wedding anniversary is going to be on a cruise and therefore but you already have Taylor Swift T Ticket concert or talk concert tickets as well so you got to go so you can take the exam I've heard it before I don't care do not make travel plans be there on this date and then uh as I post on Pat the uh if you if you can't get enough of databases and can't get enough with this class or you hate databases
1:26 and you hate bus tub and want to fix it or you're uh your sadistic and want to make torture the next round of students make bus even worse uh don't do that but please sign up if you want to be a TA with J NES uh next semester okay any questions about project
1:44 three all right and then more datas stuff more talks today we're having uh influx DB the co-founder and CTO uh so this is their third talk given uh at CMU about what they've been building on influx the first two talks first talk was what they were the new system they were building told him was a bad idea came back the second time said Andy you were right we're building a new one uh and then this third talk is basically saying oh yeah here's what we did after we we we fix things everything is based on data fusion um I'm also hosting H Camille ferreri who is a SCS Alum I think 2002 2003 um she's coming to get back a distinguished alumni talk uh she
2:22 uh been in New York City of a lot of executive positions uh and you know VP engineering positions uh for a couple different companies um she was CTO of Rent the Runway which is like the I you you rent designer clothing whatever uh and they they went IPO anyway she's she's she's brilliant she's goinging to talk this Thursday at 4:30 uh over in Gates and then next week we'll also have the the glare DB guy giving a talk okay so if you can make to Camille's talk on
2:51 Wednesday that or sorry on Thursday be great she's also a PMC for the Apache zookeeper uh zookeeper is a distribut key Value Store uh that often used for um as the backbone for a lot of distributed database distributed systems we'll cover zookeeper and other like systems like that uh in a few weeks but she worked heavily on that project as well
3:10 okay all right so uh this slide is wrong sorry I should wrong slide all right but last class we were talking about time stamp ordering not two phe locking right and the big thing about want you understand time St ordering because we're going to see this today in multiversion concurrency troll is that there's a notion of physical time like the what we call the wall clock time of when things actually occur in the real world the the order of the events in the real world but then there's also this another uh notion of a logical time of or the commit order of when things actually got saved to the
3:49 database and when we saw OCC there was this private workpace transaction were using that was allow them to sort of stage their changes and then when they went to go commit then had that validation step where we had to go figure out okay did anybody did my transaction miss any updates I should have seen or is anybody going to any other transaction that's still running it's going to miss the updates I'm about to make and we pass the sort of the validation steps then the transaction was allowed to install changes to the global data and never going see them so what we're going to see today with multiv verging it's going to basically look the exact same thing except now there isn't going to be the private workspace and The Virgins are going to hang around in the the global database
4:30 and depending on uh how we how we run transactions some transaction will actually could see some updates from transactions that haven't committed yet depending again what isolation level we're running at so conceptu when you think about what's happening in OC that there was multiple versions of tupal uh multiple uh multiple physical versions of single logical tupal in the database so a physical sorry a logical to would be like a an object identified by a primary key right Prim key says that there's only one one and only one
5:02 record that can be mapped to this primary key but then under under CC when I was making changes maybe to that tupal I had made a copy of it into my private workspace and now I had another physical version another physical copy of that single logical tupal so that's the same idea we're going to do here at MCC we now we're just going to do it on steroids um where the datab system is going to allow be allowed to maintain
5:25 again multiple physical versions for a single logical Tuple or logical object so anytime now I I want to update something in the database I'm going to make a a new logical version of of that object and in the example that I saw when we talk about OC that that new version was just a complete copy of the entire tupal into that private workspace
5:45 we'll see as we go along that's actually not a good idea and we can be a little bot smarter about it maybe just take copies of the subset of the things that got changed and then now when any time uh a transaction wants to read that object
5:58 it's going to have this this View or we'll call it the snapshot isolation snapshot view of the state of the database that existed at the moment that the transaction started so that means that if another transaction is running at the same time as you are and uh but they start start after you and they start making changes you're not going to see them because you're going to see a consistent snapshot of the database at the moment The Logical time that you
6:21 started this make more sense as as we go along and I'll say also too that we're going to we can still combine multiversion curreny control with two phas locking and OC and other protocols that are out there cuz multiversion isn't just about oh I'm making copies of things and maintaining snapshots we still have to do all the concur stuff we talked about before to figure out who's allowed to update what and when but now this the backbone of of of the way this architecture is going to work system is going to work it's going to be predicated on this idea of I'm going to make versions of
6:51 things so mvcc is an old old idea uh the first sort of what is acknowledged the first description or implementation of it goes back to PhD dation and MIT in 1978 but that was sort of in like the systems uh World um and it wasn't until a few years later then people said oh this is actually applicable to what we care about in databases with con control and then it was added into uh some existing systems so what is cited as the the first implementations of mvcc in a database would be this thing called rdb
7:21 VMS uh and then another system called interbase and these are both built a deck in the early 1980s by this guy Jim starky um he claims he's also the inventor of of of blobs like the the binary large objects I don't know whe that's true or not but that's what he says um and then actually who here has ever heard of deck nobody that was a huge company back in the day like the Google of this time uh and then they got bought by Compact and then compact got bought by uh HP and now they're basically not really if you ever heard VX machines that's that's these guys right but they were also bet because they were writing software to run on the hardware they were selling so these systems are still around today
8:00 so interbase you can get company there's still company called interbase and they sell something that's a a um like a mobile phone uh embedded database but the the sort of Enterprise code was forked off many years ago and open source as this thing called Firebird um everyone don't know why Firefox is called Firefox because when Mozilla went under or and they couldn't they want to Rebrand Netscape they wanted to call it Phoenix cuz like you know rising out of the ashes but there was some other software that had that so they couldn't call it that so then they were going to call it Firebird couldn't call it that because this databas system already exists so then they come up Firefox
8:34 right Oracle buys everything and so Oracle bought rdb uh from the carcass of deck and then they rebranded that as Oracle rdb so there's the Oracle of the company there's or the Oracle database the Big Money Maker that everyone is aware of but then they also call something Oracle rdb that's this that's the descended from this this this deck machine right so oracle's branding is not very good here and the Oracle database that every knows of is a relational database system you could call it the Oracle database a rdb uh but it's different from the brand name of
9:08 this all right so now again even though this back in the 70s pretty much every single data system today if you're going to build a new one from scratch is going to be using uh is you know using multiversion con curreny
9:19 control all right so there's two key ideas about mvcc the first is that the writers are not going to block the readers and the readers are not not going to block the writers so again the idea is that when a transaction shows up they'll be given a time stamp and that time stamp is going to say here's the time stamp of that allows you to view a consistent snapshot of the database at that Tim stamp so you won't see any uncommitted
9:46 changes and you won't see uh if if a transaction commits while you're still running all a sudden their changes won't won't materialize because those those changes didn't exist at the time stamp you were assigned when you started the system system right so that's me me my Snapshot and now since since the readers can read things at at a certain time stamp when someone when a transaction wants to write to an object or write to a tuple they're going to create a new version of that and that doesn't interfere anybody else from reading the older
10:17 version likewise when when someone is reading the older version and I want to make a new version I don't have to block on them wait till they they finish reading so we're going to allow our transactions to to basically get this consistent snapshot without acquiring explicit locks because again I've given a time set when I started I can see everything that existed at that
10:37 time and then by default by naturally or implicitly we're going to get this different isolation level that we didn't really talk about yet called snapshot isolation and again that just means that I'm viewing the database at as it existed at a certain point in
10:50 time so one of the big things that was tatted about mvcc when it came out in the 1980s is that it could support what are called time travel queries right so the idea is like if I say run this query for me but on the database as it existed three weeks ago if you have all the versions because you didn't do any garbage colle clean things up then that's trivial to do because you just figure out okay what's a time stamp from three weeks ago
11:14 let me go view the database at that time postgress originally shipped with that feature right that was one of the big things they titled when they came out 19 early 8584 uh that was like one of the origal design points of of postgress is that oh we can do time travel queries and the 1990s when they when they first started building up the open source version improving the open source version that came out of Berkeley uh one of the first thing they did was get rid of the time travel thing right because again if you don't do garbage collection you run out of storage pretty quickly right if you're not you're not familiar with the history of postgress so postgress was a academic project at Berkeley and want to guess what the first language pogress was written
11:51 in what he said c no Bas basic no not that bad or Worse meing what close lisp right and what it would do it would take list then they they run a compil that convert the list into C and then compile the C and they realized well this is stupid let's just like why we wasting our time in list just write it in the C right and so there was a academic version of of postgress and then Stonebreaker started the company I think the first version was called Montage then Monae and then they got sued for that and then got renamed to illustra uster got bought by informix so the first version of post that came out of Berkeley became this startup that got bought by inic then emerged in which informance got bought by IBM like you see how these things get just eaten by the bigger companies but then the reason
12:35 why it's not called postgress now the official name is postgressql is because in 1996 two grad students took the original academic code removed all the qu stuff and added SQL to it and then a bunch of people started picking up and actually started using it and one of the people that actually started making a lot of work on postgress is this guy Tom Lane he's seum he still lives in Pittsburgh because he was a day trader and needed the database and he started they started and post and took off from there and so like he worked I think he was part of the team that took out took out time travel queries in like
13:06 99 all right enough history all right so here's an example MCC so now we have our database uh now we see we have some additional Fields here right last class when we talked about OC we had this right timestamp to say what was the time stamp of the transaction that wrote This Record into the main table right but now we have this additional column here we're going to keep track of the version number now this is not something you actually would materialize integral database I'm just showing this for the illustration right to say what version we're actually looking at but you wouldn't actually store this the way you keep track of the versions is through these additional time stamp Fields just like OC had right time stamp now we're going to have a begin time stamp and end time stamp and that's going to scope the
13:47 the visibility range of when when a version is actually visible all right so now when a transaction starts calls begin we have to assign a time stamp we have to assign it's begin time stamp because it need again it needs a consistent snapshot and needs to know what time stamp I should use to view versions right that's different OCC OC gave you a time stamp when you want to go commit in nvcc you need to have a time stamp when you start because you have to know what you know what you're allowed to see so now when I do a r a again ignoring how I find this this object like through an index or whatever but I'm going to land through
14:20 uh version a z for this tupal and I'm going to be able to read it I should also point out to the end time stamp is is infinity or null or whatever just indicate that this is the latest version it's not bounded like the the the end the end time stamp scope is infinity so we can read this version that's fine T2 starts it gets time stamp two now I wants to do a write on n and so in this case here I'm going to create a new version of the tupal again assum I'm just making a complete copy of it and then now I'm going to set the begin time stamp to be the time stamp of of my transaction T2 when I started and then I'll set the end time stamp to again infinity or null or whatever and I install install the new update on the value but now I need to go back to the
15:04 previous version and set its end time stamp to be my time stamp right now that balance any other transactions that comes later on they'll know that if my time stamp is greater than two which it has to be because we've assigned two to to T2 that if they go start looking in the database and they see a Zer say say their their their time stamp is three where you look at begin time St an end time stamp three is outside that that that range so therefore you know that a z is not visible to your to to you the transaction and therefore you would follow down and and see that next next tupal has uh uh the next version has time stamp between two and infinity
15:45 three is is is greater than two less than infinity so this is the version you'd actually want to see all right so what's missing though how would another transaction know that this this is actually a committed version right so additional thing we have to maintain is a transaction status
16:08 table where we just keep track of here's all the T here's all the transaction IDs of the of the transactions that are that are active in my system or running my system here's their time stamp so they were signed when they started and then you have the commit status what's happening with them are they are they are they aborted are they committed are they cleaned up right so we also maintain this table as well
16:29 so now the idea is that if a T3 shows up and says should should I be able to read A1 depending what isolation level I'm running at if I only see if only if I only want to see committed changes then I know I should be looking at a Zer if I'm allowed to read uncommitted changes then I could read A1 and I would look at this status table to tell me whether is this transaction finished or
16:49 not then we switch back to T1 T1 does uh read on a and in this case here we can just read the same version that we had before right and this gives us the repeatable read guarantee that we wanted
17:01 and then we can go ahead and and commit right for both these guys straight forward now one thing I didn't mention is how we actually find the different versions for for a logical tupal we'll cover that later on yes if a transaction
17:17 like a third transaction running and it access wants to access a at some point like say the third transaction starts for transaction A1 between a z and A1 and then tries to read a will it read based off of its own start time stamp so going back here so say there's a transaction
17:40 0.5 right so what should 0.5 see well when it reads A it's going to read like it'll read the a zero even if a even if at that point a1's already written it uh so A2 does it right here so you're saying so even if A1 does it right so if A1 right and then a 1.5 reads A at some point while a a z and A1 both exist will it read a it'll read a z because a Z again
18:10 the the 0.5 is the time stamp that gives me what's the consistent snapshot of of the database at that given time stamp so A1 doesn't exist yet you know it might physically exist but logically at at time stamp 0.5 it does not exist yet so I I have to read that that old version
18:27 which is correct yes and then for like rolling back like say a third transaction starts after this reads A and then a aborts A1 aborts and rever uh reverse will it have ISC here how does that his question is uh so say we're at this point here where i'I've I've written to I've written a new version of a so T2 wrote A1 so then now transaction 3 comes along and again say they get time stamp
19:04 three T2 has not committed yet so again what should time what should transaction T3 see consistent view of the database at time stamp three all right and and that means that you should only see committed changes assuming you're running with that isolation level so therefore they won't see A1 they'll see a Zer again so you also subract metadata of whether or not that value belongs to a committed or that's this so I I would you would say all right in this simple example here I know that A1 is written by a time a transac timestamp two okay is that committed or not should I be able to read that look at this thing oh it's still actively running therefore I shouldn't be able to see that and I I should know I need to look look at the older version now I'm glossing over how you actually make this efficient but that's the general
19:55 idea okay so let's look another example so in this case here um T1 is going to do read on a write on a read on a and then T2 is going to read on a and write on a so T1 starts get get gets begin time stamp one does the read on a we gets a Zer because that's consistent view that's fine then now it does the right on a creates a new copy in here that's fine just like before and then again we have to go update the the end time stamp to be one to to indicate that a Zer is bound now or its visibility ends at time stamp
20:26 one then we contact switch over here T2 T2 can read a because again if you look in this in the status table for the transactions and see that T1 hasn't committed yet so therefore we don't see uncommitted changes so it's going to go ahead and read a z then now it's going to go ahead and do a write on a but in this case here because mvcc by itself isn't going to protect us about right right
20:51 conflicts right so so assuming there's some kind of two-base locking going on so in this case here we would recognize that because this this end time stamp is um is infinity we're trying to overwrite this we go look in the status table and see that T1 has has not committed yet therefore we're not not allowed to create a new version right because we could potentially overwrite those changes and that would be an inconsistent view or incorrect View and therefore in this case here it's going to stall in
21:20 wait then when T1 goes ahead and uh and and comes back does read on a it's going to read the version that that that uh that error is wrong should be down eror should be here just read A1 uh because that's the one it wrote before then it goes ahead and commits and now when it commits say there's a lock on that Tuple or an A that gets released and then now T1 T2 can go ahead and create the new version and go ahead and allow to
21:51 commit yes when is the end time stand assign question is when is the end the end time stand is assigned when you commit like when you call how does A1 uh I mean how how does the N sign of a z
22:05 B1 is that for for what version for a z how does how does it zero to one so going back here when so the sorry there's the the end time stamp is the time stamp of the transaction that created it right so this going back here so when he does the right we create a new version here right we have one to Infinity but now we have zero to Infinity so again if I'm following this think like a link list I'm following the version chain I would see a z 0 to Infinity okay this must be the latest version but that's not that's incorrect right so it has to go back and set the end time stamp to be whatever its time stamp is is so 0 to One
22:42 exclusive okay so assume there's no right in uh t t uh the T1 then the like the nend St of a z will be assigned uh when when A1 commits uh so your question is what when is the end time stamp of of A1 assigned say this doesn't happen this guy's calls commit what I said the end time stamp to Infinity because this is the latest
23:12 version so is this actually sterilizable ra say yes ra hand to say no ra hand if you don't know no right because what should happen if they was running in serial order going back here say we get to this point here if we were running in serial order so the N of the database is is A2
23:42 right this guy here read a z because that was the view of the DAT they saw when it started even though this guy did a right which it should have seen but under snaps isulation it doesn't then when it goes ahead and commits and now it's installing its new change and so if it wasn't a Ser this is one value it's kind of trivial but like if I was running in Sero order I should have saw this guy should T2 should have saw T one's right and then do its own right but it saw a saw the right from whatever transaction
24:18 zero so this is because snapshot isolation is susceptible to an anomaly we haven't talked about called the right skew anomaly right and again the basic idea of snaps snaps isolation says that you get a consistent view of the snap of the database that existed when the transaction started so you won't see any torn rights from from actual transactions right you won't see if they update five things you you're not going to see three and miss the other two
24:45 right if two transactions try to write the same thing then whoever whoever gets there first win assuming you're not allowed to stall and weight but this Romi is a different idea where the it's like I got to see the cons SN of the database but when I apply my
25:02 changes it would it's not equivalent to being if I was running transactions in a Serial order and again I realized me waving my hands doesn't make any sense uh let's actually look a really simple visualization so this is invented by Jim Gray and the guy who invented concr control Two Face locking when the torum W in the 90s for all this stuff right he was very good at like dumbing down
25:22 simplifying very uh complex Topics in databases you ever heard of the five- minute rule that's from him you ever heard of P99 latency that's from him or the 59s that's from Jim Gray all right so say your database is comprised of marbles and they have two colors black or white and you have two transactions that want to run exactly the same time first transaction was turn all the white marbles to Black second transaction want to turn all the black marbles to White
25:48 so when they both start running this is the consistent snapshot that they both see of the database two blacks and and two whites so therefore when the transaction runs the the guy top is going to take these two bottom ones flip them to Black the guy the bottom is going to take the two black ones and flip them to White and then now when they go ahead and commit we end up with this database database like
26:09 this again under Snapchat isation that's allowed to happen because they didn't take right locks in the whole thing right they just updated the things that they cared about and if it was running in true serial order it would really be this first transaction changes all the the marbles to to Black second transaction changes all the wers to M to White so they either all black or all
26:33 white so by itself snapshot isolation does not support is not serializable and something like postgress there's extra stuff we have to do but we're not going to cover in other systems to contort snapch isolation to make it support uh
26:48 serializability and this is why Oracle for example again when you ask for serializable transactions or isolation level you're getting snaps snaps isolation which would be susceptible to this problem this anomaly the original uh uh specification for transaction isolation levels that came out in
27:08 1992 uh doesn't mention this this problem right defines snapshot defines isolation levels in terms of two-phase locking right read uncommitted recommitted repeatable read and sterilizable but again as I showed that graph uh last class the isolation levels are sort of this branching thing and that side branch of snaps
27:26 isolation um and I had the guy that actually was the author of this he was he he was telling me that um he was at Microsoft at the time and the reason why the they missed this skew anomy because the one guy forgot to read it or something like he was too busy writing some code he didn't read the spec over carefully uh and then they they had to come back and fix it later
27:46 on all right so so the high this is what mvcc is again the idea is that we're going to create logical ver physical versions of logical tubos every time they get updated but it's not just getting a conren protocol like we saw with two-phase locking and uh and OC the the concept of versioning permeates all throughout the database system I show that diagram like here's the different layers of of the system and we building up the stack but then when I said now we're bringing in concurrency control and there's this the BL giant blob of concr control uh assumed all the other parts that's because all throughout the system it has to be aware that it's dealing with different
28:24 versions and as I said pretty much every single database system built in the last 20 years uh even maybe 30 years is going to be doing some variation of MCC and some are much better than than others so what I want to go through quickly is is here's all the design decision you have to make when you when you say you want to build a multiv verging system and you really want to sort of think about again what are the implications of these different design decisions about how they're going to affect other parts of the system so in particular how you're going to do version storage is going to have a big influence on what happens when you do
28:59 index management especially with secondary indexes okay and this is not going to be I mean this is going to be a again a brain deel here's all these different things uh you you want to do or you know you could do the main takeaway is going to be and I'll try to say this as we go along the worst implementation mvcc that is out there today Le at least I'm aware of is actually postgress so you don't want to be doing what postgress does despite me for me you know loving postgress uh it's actually the worst implementation mvcc and we'll see why as we go along my SQL and Oracle actually do it
29:35 better and every other system today unless th Fork postgress are doing it the my Oracle way all right so I was a bit hand wavy on how we're actually protecting uh objects from from two writers at the same time right but it's all the same concurenti protocols that we talked about for like you still need to bring bring all that Machinery back right so if you're doing two phase locking right you're still going to need a lock table you still need deadlock detection prevention you need all the things we talked about in the previous lectures and same with
30:02 OC whether or not you're using a private workspace for the new versions and still doing OC with the validation steps that depends on implementation time stamp ordering is the basic thing that we talked about before we're like yeah I sign a time stamp and I just make sure I commit that order and that that gives you basic uh that'll give that'll give you snaps isation but you have to do extra stuff if you want um if you want sterilizability which we don't cover in this class but we cover in the advanced
30:26 class all right next thing we got to worry about is how we're actually storing these versions so I'm just showing in lines that are in a table in PowerPoints not exactly how actually implement this but the way to think about this the version the version that you're maintaining for a single logical tub it's essentially a link list so the version chain is going to be have pointers to say here's the next version that you need for a given tupal so there would actually be a field uh with with a
30:55 a record ID more or less that's going to tell you here's where to go find the next version as you as you Traverse along the version chain it'll be a single Direction link List Right double double link list is you know for this you don't really need it doesn't really help you it's just extra maintenance so the entry point is always going to be at the head of the version chain but then now the question is going to be what order do we do we store the versions
31:17 oldest to newest newest to oldest and then what are actually the versions themselves and where are they actually being stored so there's three approaches to do version storage the the most basic one is a pen only storage where every single time I make a new new version I copy the old one insert it into the table as if it was a real tupal another tupal and I just keep track of the the version chain in the
31:43 headers right this what I showed in my example before this is actually what postgress does the next approach is to do time travel storage which is basically like a pen only storage but instead of storing the new version back in the same table I'm going to have this separate table that's designated as as the time travel table and I'm going to put all my versions in there so I'll have a main table that always has the latest version
32:07 or the the oldest or the newest version depending on the version chain that's always going to be in in the main table and then they're going to have a pointers to these auxiliary tables where I'm that's going to put all my my
32:20 versions and then the last one which is actually the best one is that you basically instead of storing entire tupos you just store deltas like think of like a get diff or or diff um so if I have a thousand columns and I don't update one of them and the two other approaches I have to copy all 1,000 columns but under Delta storage I only stored the one the the the subset of the columns that actually got modified and with with their new values or previous values and I'll store that in a separate
32:47 Delta record storage space so the top one is the worst case don't do this right because as you see as you go along it's going to have a bunch of storage issues bunch of um uh it just makes everything more more expensive the reason why postest did this is because the idea of postest in the 1980s was there wasn't going to be a WR ahead log which we haven't covered yet that's next week but there was or yeah next class uh there wasn't a log
33:14 that says here's the changes that I'm making they said okay well the tub themselves that's the change so recovery would be instantaneous because you just come back in theory and then you would have all your tubes that you that you were modifying and working on just sitting in your tables of course that's really slow because we'll see there'll be a bunch of random wrs that that'll be bad and so the right head logs make a better approach and they they've added that later on but they still have this idea of like every single time I make a new make a new version I make a copy of the whole
33:42 thing and they have some hacks to try to make this be faster if you can try to keep things on the same page we'll cover that in a second so the bottom one is what you want to do but we'll go through each is one by one so again a pend only store just says that every I'll have in my I have a single table right so every dat every table in my database I'll have S one table space for all that and then now anytime I I make an update say I make an update to version one here or A1 here
34:08 I'll make an entire copy of the of the record down to the new to new space in the table install the new value and then go update the version chain now to to point to the new version I just created
34:21 and this example here I'm going oldest and newest like a z is the oldest one so I I want to find the newest I follow along the the version chain to I find find the one that I want and then the pointers are just record IDs it's going to be a page number and a page number and a slot
34:37 number the version chain ordering actually has big implications for performance as well so if you do oldest and newest that means that every single time I do a look up say I follow an index I look up an index I get now a uh I get a record ID that's going to take me to the head of the Virgin chain now I got to scan along that virgin chain to I find the one I want and again you're looking at the the begin and end time stamp that I showed in the beginning to determine whether the version you're looking at is actually the one you want or not
35:05 right newest to oldest is where the head of the version chain is going to be the the latest version so now when I do a look up in the index and say I'm just I just need the latest version the first thing I land on when I when I do the lookup is going to be my the version that I want so that sounds great the downside is now every single time I update a tuple I have a bunch of indexes I got to update all their entries now to make sure they point to the the new
35:32 head if you're doing Delta storage is actually not a problem because the the if if you just you just overwrite the head is always be the latest version and everybody always points at that if you do a pen only then I I make a new version that's now A distinct physical Tupa that's in a new location and now I got to update my my indexes to point to
35:51 that so these these These trade-offs are these choices aren't are aren't um aren't uh independent from each other all right so time travel storage is basically the same thing as a pen only storage except now instead of storing the the physical versions in our main table we have this whole separate table it's basically just just another table but that we're going to stir all all the previous versions from this so I update this thing
36:18 A2 uh I'm going to make a copy of it into the the table the the time travel table and then now I just update the the the master version in the main table with the latest version that I'm installing here and then I update the pointers now to now point to the next one
36:39 here take I guess why you would do this yes what you change say it again what if the change affects the index ke what what if the change affects the index keam key index key oh the index key uh
36:54 if if you basically Tre that as a delete file an insert so you say say you update the primary key right well is that really almost a philosophical question is that really the same logical Tuple well no the primary key has changed so it's really a delete of the old the old record based on the old primary key then insert with a new one so you lose that vergin chain continuity but it makes the bookkeeping way easier to do that if you change the the the secondary index key depending on how it's actually you're actually keeping track of the SEC index we'll come to that in a second you may not have to update anything I me you'll update the entry but you may not have to
37:37 um actually you have to update the secondary index but like the key the value of the of the index will still be depending on how you organize it will still be the same could be the same so you said like uh the time travel and previous one like incurs uh a lot of waste because you need to cop but I don't see you copy like the unified
38:04 into right so it's question so his statement is I made I made a big deal that pening time travel storage waste a bunch of space because you're copying time TS but I have this B1 here and it doesn't have an entry in the time travel table what's up with that garbage collection we'll get get to that in a second mvcc doesn't come for free right it's a great idea and it opens up makes things a lot easier both the implementation side and actually from the application stand point but someone's got to clean things up CU otherwise you just run out of space so you assume B1 has been cleaned up cuz no the transaction could there was a b0o no transaction could see it no there's no actual transaction that where that Tu will be visible to it therefore we wouldn't reclaim the
38:42 space yes from what I understand this type of table essentially is just doing a pen only change build a separate table so how is it significant better than theen only her question is this basically seems the same as a pen only which is correct but instead of putting it to the main table you put put in the time travel table why is this a good idea or why is this better than pen only so I'm not saying it's better than pen only what I'm saying is
39:04 that this comes up in systems that didn't have multiv verion to begin with like SQL Server the when they was originally single version two locking and then oh want to add MCC you can graph this thing on still keep all your single version stuff here and everything still works the same but now if you want to go you know see older versions you have this auxiliary table you can just follow along and read so in the system that didn't maybe weren't originally designed with multiversion they would use this
39:32 approach so as the downsides you're making en TI copies of tups you have thousand thousand columns I only update one of them uh you still have to pay the penalty and so this example here we're going from um we're going from newest to oldest uh so SQL Server works that way there's another system called sap Hana they were doing oldest and newest so anytime I did a new version I would make it actually in the time travel table and then when I ran garbage collection then I would basically compaction then I would promote it to the main table when it was the when it was the
40:10 latest all right again the last one is the Delta storage right the basic idea is that now every time I do an update I'm only going to copy the The Columns that got modified uh with their their previous values and I'm going to store that into the the this Delta storage segment think myo calls it the roll back segment basically same idea it's like an undo log so in this case here the original value of A1 was 111 so again I realized there's only one column value but you know assume there's a thousand columns you're doing the same thing but then now so I'm going to store what what the value was before and the version information that was was here when it was in the main table then now I I set a pointer to that and I overwrite the in the main table here's the latest version
40:52 of this tupal again that's fine if anyone wants to see the older version you look at the time stamp and say this one's not Vis to me you follow the pointer to find the the Delta set and you're basically now like replaying the log to put it back into the state
41:05 before right same thing I updated again uh then I just I update with the uh a new new entry in there right so the this looks and smells a lot like the log structure mer treat stuff we talked about before
41:23 right but in the log structure Mer tree the idea was I was a pending the the new entries the new changes that I made this is the new changes get applied into the main table and then the previous value
41:37 gets put into the version version uh the version storage right so sort of the same but not exactly you can imagine you could piggyback you could combine the two and and sort of achieve the same thing yes so like if I modify a so say I I have a trans SE that modifies A and B together that's going to be one entry in the Delta table the question is if I if I have a transaction that modifies A and B together would that be one entry in the Delta table no because there' be
42:10 again think of the Virgin chain is like for a for a single logical tupal so A or B here's the verg chain for that because think about what would happen if now if I if another transaction only modifies B
42:23 then they would come along the version chain they would see changes to a and they may actually not be visible to it or like makes things more complicated Nobody Does that but if I have this trans and modifies both uh two PS that want to RT it back with the Delta storage um how would it know that these two entries for A and B are actually for the same transaction we need to R them together the question is if I modified A and B and so the old version got put into the Delta storage now now I need to roll back that trans ction how would I know that these are the changes I made
42:59 because I would see the end time stamp of the the entries I'm putting in there would be my time stamp of my transactions therefore I know this is the one I wrote therefore I got I got to reverse them so I basically scan through all the Del changes and find the corresponding time stamp your question is would you scan through all the Delta changes and find the corresponding time stamps um in naive implementation yes you can imagine
43:22 and you actually you'll see this in P4 you could have the transaction record in its own local storage here's the changes that I've made therefore you know you look and see WR them right away but yes to your point that that's a shortcut right that's a efficiency uh Improvement like you could just say you can always go back follow the version chain and find the version that you created if you created
43:43 one right because the day will guarantee that it's not going to it's not going to clean up or garbage collect or reclaim the changes you made until you finished because then that would be you have other problems yes um where are the time stamps question is where are the time stamps stored I'm not showing the example here but they'll be in the TU the headers of the records themselves we'll see this in
44:09 post Okay cool so now we got to clean we got to clean things up with garbage collection because otherwise we're going to run out of space so the idea is that we're going to reclaim space from the old versions that no other transaction needs anymore meaning there's no active transaction that can view a a version of of a tupo therefore there's no reason to keep it around unless again unless want time travel quer is which most people
44:35 don't um the only time that you ever want time traic ques is like if you get you were getting audited or something like that right like if you're like a you know secur exchange most most people don't need it um so we want to be able to reclaim space and be able to use that for new versions and new data so the a a version is deemed uh reclaimable if no other transaction can see it under snaps isolation or the version was created by an aborted
45:03 transaction right we could set a flag say this thing from a board transaction should not be installed and then everybody scan along can just remove it so the two design STS we got to consider are how do we look for the inspired versions I said one example here I just keep track of the things you made and then you go reclaim it that's one approach
45:22 right and then how does it sign how do we determine when it's actually safe to rec the space or storage for uh you know for for records so to two approaches to find things is to do Tuple level um garbage collection where we'll just look at the versions themselves and say is this thing actually visible by anything that's running right now yes so I had a question about like the written changes uh so if within one transaction we we write a twice appear in two entities
45:59 just his question is what happens if you write to the same record twice uh if the data system is smart it would say it would overwrite the first one right now the things get tricky like if I allocate space if I if my first update updates one column and I allocate some memory you know some space for that one column up then my next update on the same logical Tu updates a thousand of them then I got to it's a little more bookkeeping to manage that but in general you think about it it doesn't make sense for you to have multiple versions for yourself right because again when you commit then you're installing whatever the LA the version you know the version that you created
46:38 nobody cares that you had intermediate steps to get there we'll pop up pop up in post to the end see what they do I think they just overwrite it again in post it's easy because it's a pen only and death it's
46:52 hard all right so the first first level the first type of garbage collection is dupa level but again we're just going to scan through all the versions and try to find something that that that's reclaimable and we'll either do this with a detated dedicated worker we'll call Background vacuuming or we'll do it while we're scanning data right so Cooperative cleaning and then the other one is what I was suggesting to her is that you just have all your transactions keep in track of like here's the things here's the versions I
47:18 invalidated tell some garbage collector like okay by the way here you know here's things you you you may not be able to clean right away because there may still be something running if they can see it but but eventually you you you go ahead and clean this
47:31 up so in the first case here the back on back me the idea is that you we have a separate thread that's periodic going to wake up and look to find recl versions all right and no matter what storage scheme you're using a pend only Delta storage or time travel this this this works just fine so say we have two transactions T1 and T2 and they have different time stamps so now there's this back backround vacuum thread our worker it's going to uh look at the version numbers from its from action
47:59 transactions and then going to literally just do a squential scan look at the begin and end time stamps and say okay I know I have transactions with time stamp 12 transaction with time stamp 25 are there any versions of tupal that aren't visible by these two transactions in this case here the a00 and B 100 are not visible so we just go ahead and delete them and reclaim the
48:22 space all right well this sucks if I have to scan my entire table every single often right blindly looking for for things that got modified so you can be a little bit clever and maintain a Dirty Bit map that keeps track of you know set a bit to one every time a page is modified the last since the last time I ran the vacuum so now when when the vacuum wakes up he says okay I I just look at my my Dirty Bit map and only go fetch those pages and go see whether uh go prun out anything I don't know how they were modified because there's only a single bit but I need to look in there to figure out if there's anything I should be cleaning
49:00 up this is what basically what postest does right so there's a bit more cleverness to it like if if you've updated a t if you updated a table and you've touched 25% of the tbal or 20% of T by default then the vacuum will go look at it right but this is basically how how it works or you you can call vacuum from the command line from the terminal it'll it'll kick it off as
49:23 well with cop cllean the idea is that the the worker threads are going to know here's the things that are visible to me uh visible to any actual transaction so now when they scan along uh the version chain if they identify
49:38 any uh any any version that's not visible to any other transaction then you go ahead and and prune it so think of that there's a now there's a global global time stamp that says here's the the lowest time stamp of any active running transaction so now as you're scanning along if you see that anything is is less than that uh then you know you go ahead and and clean it up and then you just update the version the the index now point to it so let's make your scan slower but now you don't need a separate background thread yes
50:11 to L question do you need acquire a lock on the like The Logical Tule yes yeah and you you update this thing as well yes because otherwise people two people can do the same thing so this works great uh but you still need this thing to kick off every so often because if I say I update I update a record I create a new version it invalidates a previous one and then no one ever reads it
50:39 again you're never never going to reclaim it SQL Server calls those Dusty corners and you have to again every so often then you kick off the background thread and clean things up and transaction level GC is what uh I already mentioned again you just keep track of like here's all my transactions here's the things that they modified so I update A1 A2 create A3 uh and just keep track of the old versions there like it be like a record ID or offset or pointer to say here's the thing that I
51:07 invalidated go check late some later point right same thing update B add it to my entry in here and then now when my transaction commits I get some commit timestamp and then we just pass this information along to the vacuum that says okay if there's any timestamp less than 10 because that was my begin timestamp
51:27 uh then these things can get cleaned up right this is rare uh most systems do the the the background thing the background vacuuming um but again if you're doing Delta storage it's easy because you don't have to scan the entire table just go scan the Delta
51:49 record right and it's easy to clean that up because now you don't want to like um problem the pen only storage as well as you're as you're vacuuming now you have holes in in your in your storage space you have to compact the pages and post doesn't reclaim space unless you run vacuum full uh so you could have a lot of empty space in there where whereas if you're doing the roll back segment of the Delta storage like my SQL you just blow away the that that Delta storage
52:14 and leave all your tables by themselves all right so next thing we got to worry about is what our indexes are pointing pointing to right so the primary key is easy the primary key is always going to point to the the version head no matter what storage scheme you're using right
52:32 and as as as he was asking before the way you just treat someone updates the actual primary key itself you just treat that as a delete followed by an insert because again conceptually or philosophically it is a new new tupal
52:46 right it's the secondary indexes that are problematic because depending on what the secondary indexes are pointing to now when I and depending what my my version ordering is like newest oldest oldest to newest now when I update a record or logical toook create a new version I may have to update every single index now the point to the new
53:12 version right and so the I I'll post this link on slack or it's in the slides the great example of of why you need to understand what the hell is going on inside of a database system it's this blog article written a few years ago by Uber
53:27 all right the title of the blog article is why Uber engineering switch from postgress to mySQL the real title is why Uber engineering switch from MySQL to post back to my SQL because they were running on my SQL before they they were having scaling problems like any other startup they hir some guy who was really big in the postgress which is fine it's a good database system but they didn't fully understand what postgress was doing on the inside and what myo was doing the inside for their workload and their workload was actually the worst case scenario for postrest so after they deployed postrest they realized oh that was a huge mistake and they had to go back to my Sequel and I'm sure they paid millions of dollars to do this they should have paid us a millions of dollars we told them not we would told them not to do it and save them save them a bunch of time right so this again this why even if you don't go off and work on datab systems in in your career
54:10 you need to understand what's going on the inside and what the DAT is going to be doing because when you start pushing these systems really hard these different design decisions are going to can can cause problems all right so if you have second indexes the question is again what are they pointing to right the keys going to be the same key going to be whatever the index attributes that I have the question is now in the value what what is that so there's two ideas or two two two approaches one you have a logical
54:36 pointer that just says here's a here's a some kind of logical identifier that they'll help me find that I can use to find where the actual physical location is for the head of the Virgin chain simplest thing to do is just store the primary key my SQL does this so when you do a secondary key secondary ke look up uh on that index you get out the primary key which you then go probe the primary key index to go find out where the actual physical data is
55:05 located another approach to CH use a tu identifier think was a synthetic ID Nobody Does this but because you need to maintain another another index for that it's not worth it post stores the physical version physical pointers to the head of the version chain right and you and use that to go find exactly what you need so again so say we're doing this say we're doing a pen only newest to oldest so post is oldest and newest but the the the idea is still still problematic all right so again when I do look up my primary key index you know get object a I get a record ID that's a page number and a slot number as we talked about before and I land exactly to where I want the head of the version chain and I just Traverse the version chain to find the version that I want if I do a secondary index look up when I call get a I get the head of this version chain or the record ID like this but again in OT databases you're going to have a lot of indexes a lot of secondary indexes
55:56 right so now all of these now are going to be pointing to the head of verion chain so in this case here if now I update the Tuple even if I don't update the attribute that the secondary indexes are based on because now the head of the vergin chain is going to change right with with a new physical address I have to go update all these secondary
56:17 indexes so post tries to be a little bit clever here and what they do is actually post will have a for every single version they will have a another entry in the in the index but they try to be clever they I think they're called Heap only updates or hot Tule updates where if the new version because it's a pen I create the new version if it's in the same page as the previous version the latest version then I don't need to update the the index I just have now in the in in the page itself when they follow the version chain land in the page that says oh by the way the you you came to me through an index but the version you really want is is is the next one follow that pointer so post guest won't actually update the secondary index if the if the if the new version is in the same page that happens maybe I think 40% of the time we we've seen in in
57:09 experiments right so so it's again it's sort of hack they have to do with because they're dealing with their pend only storage I what my SEO does is that the second index will give you the primary key and then the the the primary key will give you the record ID the location so now anytime I update anything down here I'm I'm only updating the primary key index I'm not updating the uh the secondary
57:32 indexes my Caso is a little more complicated because my SQL because in INB actually the the leaf nodes in the B plus3 because it's index organized storage that's actually the data the tups so in that case when you you're not really getting a record ID if you follow the primary key index you're getting the tuble but the basic ID is the same yes so why adding another layer of IND direction would cause problem ID because like here you if you st the primary
58:00 index you will go to another query which is essentially another level of IND Direction but if we add another layer on top of those uh record IDs we can redirect all the secondary index to that ID then every time you update the record we update both the index as well as the like the pointing to so it's it's statement is instead of what if I did a
58:28 the secondary index points to a tupal ID and then there's another lookup table that Maps the Tuple ID to the the physical location now everybody all the indexes just store the Tuple ID is the value portion and I have another another I have that map to tell me where to go yeah it's another
58:46 index but you don't have to go through the B plus this is very it's a hash map sure it's a hash table it's another another thing I got to maintain right it's it's additional Machinery additional storage bition computational space or computational uh
59:07 overhead where like the the the primary key index look up is probably good enough right it's just it's just not worth it again b+3 if for the large fan out it's not going to be that expensive to do a single key lookup right Traverse down land the B plus Street and that everything I need is
59:28 there your primary key index actually could also be a hash table as well I don't recommend it but you could right there's nothing stopping you from doing that okay so the with indexes the the multiversion information like the the begin end time stamp that's always going to be in the in the the tupes themselves most systems
59:55 don't store that with in in the keys part of the um as part of the the part of the index again the exception would be something like postgress where they store some version information to so that way I you don't have to actually Traverse the vergin chain you you can say you can do a look up on a on a key and a version within the index and then jump to the exact offset the exact tupal version you want without having to Traverse the chain because again if your version chain is spread across multiple
1:00:23 Pages now what what what should have been you know a single page lookup for one tup can be a large scan and that's going to crush performance that's why post deal deals with that but how they're going to handle uh duplicate keys from different snapshots that you that gets pretty tricky as well
1:00:40 right so say transaction here wants to do a read on a and another transaction wants to do an update on a so if I for this guy does the update he would again follow the version chain and down here to A1 create the new version and then update the pointer right but now they're going to delete
1:00:58 a so in this case here again I can I set a little tombstone in the in the in the tual head or say this thing has been deleted we know how to do that from from previous previous lectures right then now I commit another transaction comes along and wants to insert
1:01:15 a so now I create a new version here and the I need to make sure that if another transaction is running or case a T1 it's it's should C A1 because that existed at the time that it started but now if anybody else comes after that I need to make sure that they don't see uh that should be that's a typ sorry that should be a typo should be
1:01:39 that should be A3 right so any transaction comes later on with a time stamp after 30 make sure I when they see A3 and any transaction that's still running the pass I need to make sure they see A1 but in my index unless I store verging information up up in there
1:01:55 you know they say oh get go give me key a if they if if depending on how things are ordered in there they would maybe land the first one and that's actually not the version they want they would Traverse along the version chain and see that thing oh this Tu is actually deleted but they would we actually be seeing A3 at a later later
1:02:13 timestamp so there's some additional information we got to keep track in the index to to handle this this case postgress always does it because they want to make sure that you can jump to any point in the virsion chain very quickly
1:02:26 but if you're not doing that you still need to maintain version information so that you can jump to when you have discontinuity between uh same values in the index but different logical Tuple in the database okay so I think um a bunch of these we've already covered right
1:02:50 um right so you you basically what happen is that when you do a lookup sometimes you may get back multi multiple entries with with a single lookup and then you you have to follow the version change to figure out what you're actually looking for yes so say if I have like something like a b index on some twole and I have a transaction modified which actually leads the index plus stre to like merge or split um how do I revert back to the original to like the previous ver the question is say in this example here where I called called
1:03:24 like I this A3 does an in does an insert creates a new version CA this Leaf node to to split how do you roll back to the previous version of of the B+ tree you don't well first of all when so
1:03:38 so uh say this guy so say this guy aborts T3 so yeah so I need to go clean up that that entry in the B+ tree but you're not going to immediately do that right like you would you typically say you would mark this transaction as as is aborted you hand that information to the garbage collector and then then some later point the garbage collector is going to come through and sweep through and clean things up right and then now
1:04:05 basically the the the cleanup process in the index is is no different than a transaction doing a delete for you know for you based on the application request so when the garbage C goes through and says okay here's a bunch of versions I don't need anymore let me go clean up the indexes right now the garbage col is calling delete on on the on the index so triggers a a a merge then it just
1:04:29 happens what about if I had a small value for A1 so it's inside this Le and then I change it to like a really large value which leads it to like which leads the value to A1 to move to like other Leaf node because it gets bigger and it needs to be moved to like other
1:04:47 pointers okay so question is if I say let's not do with a lot deal with this example here say yeah so say doesn't update on so say now I update whatever this the value that this index is based on to now be really really big
1:05:02 so so what would happen here well in my example here you don't do anything because the well actually no you would treat that as a a uh you treat that by as a delete followed by an insert into the index so but the sorry
1:05:19 second at the moment you do that update you don't delete from the index cuz it's still correct at this point cuz it's Still Point you need to still point to the older version because another transaction mayble to follow that along so all you're doing when the transaction is actually running is that you insert the new entry into the index and then it would point to depending on the scheme either the head of the verg chain or the
1:05:41 if it's post you point directly to the version you just created right so so then at some later point when the garbage collector kicks off it would say okay I'm I got to go clean up A1 here but I and I know that I have an index based on this table so and it's based on this attribute so what was the value of the Tuple at this version for that attribute and make sure I go ahead and delete it in the index if I know that that no other version needs it so at the garbage collection you would you would then go clean things up because you still need the indexes to be uh navigable so you can find the version that you want based on the different
1:06:16 attributes this what I was saying before that like the when we talked about like sort of before we talk about multiversion was like oh yeah here's your index here's your data just have them point to each other and then you do deles and inserts no big deal right now with the mty version you got to keep bunch of crap around because you someone's got to be able to go see the previous
1:06:34 snapshot so in the garbage col that's when we go tidy things up going back to what I think you were saying before though it sounds like you were saying if I if I care about the split or merge how do I revert that back I don't care about the physical structure of the index
1:06:48 while I'm doing all this high level transaction stuff so if the index wants to split or merge I don't care right when I do my operations on it to get moved in and out as needed if it wants to do it it does it but I don't need to guarantee when I roll back a transaction that I end up with the exact same physical layout of the index as it exist before the transaction run I don't care I only care about the logical contents at this level right there's a separation between what's what's in the table uh sorry there's a separation between what the The Logical I review what The Logical contents of the index are versus its physical layout and we have the flexibility where the the index can change things around as at once and we don't care
1:07:25 same way like if the the data ties to swap out pages to disk because they ran out of memory doesn't affect the the correctness of our of our transactions it'll make things slower but we don't care about the it won't affect
1:07:41 correctness like I I can riff all day on this transactions are wild it's like there's so many different levels I think about what's what's going to happen here what's going to happen there uh and again this is why doing this is really hard and people pay a lot of money for this and you make it distributed it all falls apart makes it harder all actually this is basically what I just said right the DBS physically is going to lead tual from the database only when all the versions that are logically logically leaded from the logic Tu are not visible right
1:08:11 there's no right right conflicts here because it's just F first rer wins right and then we just need to keep track of that we have a way to say that a a tubal has been deleted at some point in time usually you know set a delete flag in the header and then the end time would also to Mark like when the visibility
1:08:29 ranges right and the flag or the tombstone tual so I'm kind of rushing because I want to get through the should actually pop up and post show you guys some stuff right but here's a table we we put together a few years ago for a paper on looking at all different implementations of mpcc um and you can see on vergin storage the the real standout is is uh where's postgress postgress is a pen only hecaton and NB and these other ones are doing sort of the same thing but they
1:09:00 are you know they're they're doing this in con distribut a system um and Heaton is doing it because they were trying to do graft onto SQL Server to add uh in memory storage for that right so a penol is is going to be a bad idea for most systems actually hydr is using a pen no they got rid of that and they switched to uh use Deltas like
1:09:23 hyper Okay so let's see if my laptop doesn't ah good so we're going to do this in in post first sorry and then then we have time you can do it in my SQL so we're going to have a simple table that has
1:09:53 uh A Logan simple table that has two tuples right so now in postgress remember we we saw that ctid field before right it was this hidden field it was it wasn't actually being stored but it would just tell you the the the the page number and the slot number of a tupal there additional fields for the for the begin end time stamp right so they're going to call them X Min and x max they're basically the same thing and the number there is going to correspond
1:10:26 to the the time the transaction ID that created it so what we're going to do now we're going to run two transactions so I hav't talked about how to do isolation levels but basically in in postgress when you call begin transaction you can set what isolation level you want so we're going to run this this the one here at the top and read
1:10:49 committed uh and run the bottom one and recommit it as well so in the top Transaction what we can do we're going to go grab do a read on one Tuple right the first Tuple so again we're going to get the X-Men xmax and that tells the range the ID and the value is the actual defined by the
1:11:15 user so now I can also run this command this is the postgress idium where I can run uh transaction current or not did I hang it there we go weird try to connect again oh see me Wi-Fi that sucks do you know why WI-Fi is kind of
1:11:48 dicey what was the first University had Wi-Fi internet us and it just you know has not they've UPG it's gotten better over the years I should shouldn't knock get that but when I first started it was it was dicey all right so there we go all right yeah so here we're in transaction and we see our T we now we have we get our transaction ID 1457 so now when I do an
1:12:09 update on the on a tupal right now if I select it back now you see that the there's a new version at let me Zoom this down ah can I scroll up can't scroll up I can this way hold
1:12:35 up right so when I first did the select the X-Men was 1456 the xmax was zero and then the record I was looking at the physical version I was looking at was at page page number zero offset one right so now when I select it again
1:12:50 now we see we're at page number zero offset three because it created a new version of this set my uh the X-Men time stamp to be my time stamp set this one to zero I don't think I can get back to the previous one but I know I know it's going to still be there because if I go to the bottom transaction here and say we get first get what our time stamp is all right we're 1458 one more than the last one great and I go retrieve that same
1:13:16 Tuple I see the old version that's expected right because again under snap isolation I can't see uncommitted changes of of the of their transaction so this one is this one is C 01 right but now you also see we set the xmax to the time stamp of the transaction up above to telling us that the the the visibility this thing has is is uh
1:13:41 finishing but I can still see it right my time step is 1458 because I'm doing a look up to say okay who wrote this is that transaction committed yes or no oh they haven't committed then therefore this is visible to me even though the range is stopped or range is cut
1:13:58 now let's see whether we can actually read the the other version right so I'm going to say you can say tell PR Give me the give me give me all the data at CTI CTI 03 so I'm telling it I want to see the data at page zero offset three should I be able to see it yes or no he says yes raise your hand and say Yes or is going to say
1:14:21 no no right because post is enforcing that okay yeah you you know there's something there but you can't see it so I'm not I'm not going to show it to you whereas up above I can see it right maybe ibe need to do this so I can prove that I'm actually seeing it
1:14:41 right but let's see if I can see the older version like this right I can't physically it's there logically the transaction can't see it all right so now uh so we've already updated the tuble let's see what happens when the bottom guy tries to update a tuple right what should
1:15:03 happen hang yes because the top guy above has the right lock on that tupo The Logical version not the physical version and therefore the DAT system knows says I can't allow you go ahead and and update so now when I come back up here and I call
1:15:22 commit I'm able to go commit and then see immediately this thing unlocked you tell you how long it took it waited 17 seconds right and then this thing's allowed to go ahead and update so now what version should the guy at the top
1:15:41 see thing he disc committed what version of the guy the bottom see H you want just wrote yep right so now you see we have a new physical version at at page zero offset four see the X-Men X-Men X Max and now the same as our time stamp uh both of them and then you see the new value that we just put in but you see that when we did the update right this guy set it to 101 or we're just adding one to the value was 100 this guy set it to 101 but this guy was able to read that update
1:16:19 from the other transaction saw 101 and then updated to 102 yes ma is 1458 so question why is it 1458 so why why is it not Infinity this is post internals I don't fully understand right because if I go ahead and
1:16:38 commit bottom one updated I kept said the same is it because it's a there's extra metadata they keeping track of like the order of things but the the nuances don't really matter because now if I if I run [Music]
1:17:00 vacuum on the table right then it sets it to zero right because it said I this this is the latest version right because the idea is like I think if it's the same it has to say okay this thing's in Flight I don't know what's going on uh go look at the status table and say what what's the status of the transaction and then when the vacuum runs says okay well 1458 equal 14 like X-Men equals x max
1:17:30 this transaction committed so let's go ahead and set the the the the xmax is zero because now we know it's the latest version all right so that's so we were running with read uncommitted or sorry that was read
1:17:42 committed let's reset the database and now run our run transactions under serializable isolation so again under under regular isolation it doesn't handle the the right skew anomaly right but under uh under cable which post's implantation is it's been shown wasn't I think I don't think it was correct when it first came out and then they fixed it so it is correct so here now we have our two transactions running 1462 and
1:18:19 1463 so first I'm going to do is have the guy at the top of update the um update that same record so I didn't show you returning Clauses here but see how I say update transaction demo set value value plus one where ID one and then there's a returning Clause you can put whatever you want there to get back like here's return also the values that were that were part of this tle you can put anything there right you can put in you know anything would be in the project output select output all right so now
1:18:55 now let's go down to the bottom right and again we cleaned everything up he's seeing the old version right and I'm just adding the transaction ID here 1463 so again he's seeing the the original version of this tub and you see that we set the time stamp got set by the uh the the the end time stamp got set by the transaction at the top all right so now let's have the bottom guy try to update the same TB
1:19:24 what's going to happen so he's gonna hang yes because again he's waiting to see the outcome of the transaction up above he knows that there's a right conflict in some systems it would say okay you're you're trying to write the same thing and immediately abort in this case here post is trying to wait to figure out okay what's going to happen from the guy at the
1:19:50 top all right so now what happens if we commit what's going to happen should the bottom guy be allowed to commit make it change no right because again that it was able to read the data in the previous version this guy then updated it now it's trying to do an update by reading the previous value of it but again even though there's no there's no application code here between my different queries
1:20:23 we leak to the outside world that the the version of the database at the when my trans started the value was 100 now I'm trying to do an update to it based on that value 100 and set it to 101 but the guy up above already set it to 101 so again even though I know that these are commutative you got to think about like I got back this this this data in my application that value was equal 100 and then I decided to do something the data doesn't know that it just sees that you're trying to do an update on the something got updated before and but you read a version of the data that existed before the one the guy at the top
1:21:03 committed so that would violate the serializable ordering the serial ordering and therefore the data Sy will report your transaction all right one more demo we can keep stick with post we want see my seal let me show one thing in in post post is gonna lie to you too
1:21:26 okay so isolation levels are not uh they're not Global right so I can have my first transaction at the top he's going to run with serializable my transaction at the bottom he's going to run run read uncommitted I'm got
1:21:41 to here we go so the guy at the top is going to read data right see the St as we expected guy at the bottom sees the same thing that's all fine guy at the top is going to update now to
1:22:03 the it's going to update the updates the tupal and return back the transaction ID right that's all fine now the guy at the bottom does the does the same update what's going to happen he was allowed to do
1:22:28 it oh sorry but he's updating two that's different sorry but now when I when I go ahead and run a select he's seeing the the change that he made but he's not seeing the change from the guy above well that's expected right cuz the guy up above sorry that's that's unexpected because the guy up above made a change to the database
1:22:55 we told postr we want to be able to run and read uncommitted so what does that mean we should should be able to see uncommitted changes but post doesn't let us see uncommitted changes if the top guy goes ahead and
1:23:10 commits now when I run this now I see the change from the guy at the top so postris actually can't even give you read uncommitted because it would do they have to do more work like to make you be able to see uncommitted changes and it's not worth adding that so like you get you get recommitted for free even though you're asking for uncommitted so it's like the reverse of Oracle Oracle says you ask for something higher and they give you something worse or lower in post you ask for something worse and they give you something better for free
1:23:43 because they don't want to write have to write additional code so that you can just go see uncommitted changes unnecessary what if the above transaction is also read uncommitted would they change anything this question what if the top transaction was readon committed would that change anything no because the isolation depends on what you see not what how you affect other
1:24:02 people okay yes is it really for free terms performance he question is it really for free for performance it's more like um yeah so to his point he's correct like uh no so so like you would so you still have even though you run runed done committed you would still have to take right locks to protect two guys writing at the same time
1:24:33 right if you don't so so like they're already maintaining these time stamps they would have to write extra code to say make sure I see the latest version and that just it's more code you maintain for this lower isolation level it's just from engineering perspective it's not worth it so is it for free I mean from engineering of yes performance reason maybe you could be a little bit uh a little bit faster but again the way they're doing so they're doing old Sous
1:25:03 so and as I said in the index they're always going to have pointers to to uh every version as long as they're not in different pages so it's not like if I was doing oldest and newest where I always had to Traverse the Virgin chain and I didn't have those extra pointers I always had to Traverse the V and therefore I just got whatever the first one I pointed that and I'm done yes that would be faster but they're not doing that they're they're they're jumping anywhere in the version chain so therefore you might as well go get whatever the version you're going to get anyway it's just from their perspective
1:25:31 the way it's implemented there is actually not a performance difference okay all right so uh again if you want to play around myle we can do that afterwards um so as I said the mbcc is super important um it's so important that like even systems that don't support transactions are doing some variation of it like the nosql systems uh and it's again it's not a single decision like okay I'm going do this one thing and and and I'm done you really want to design the system from the very beginning to know I'm going to do with the multiversion I'm going to do transactions and that's going to affect
1:26:04 all all parts of the architecture all right so next class we're talk about logg and Recovery basically now if we crash how do we come back so next class is how how do we prepare ourselves for a crash and then next we talk about how do what how do we deal with a crash okay I need something refreshing when I get finished manifesting to cold a whole B like Smith and Weston one Court and my thoughts hip hop related WR a rhyme and my pants intoxicated lyrics are quicker with a simple Mo licker since I'm a city slicker play waves are picker rhes I create rotate at a r too quick to duplicate feel bre at a skate mikir and height when I hold it real tight then I'm in flight then we ignite starts to boil you I heat up the party for you let my girl R in my mic down with oil W still turn with third Dee Burns for one man I heat up your brain give it a suntan so just cool let the temperature
1:26:57 rise to cool it off with s eyes [Music]