Hey traders, this is Tosh Bradley. I go by T Bradley 90 in the My Investing Club MIC community. Right now we have a very special holiday discount sale going on for MIC members or anybody wanting to join. We have $200 off our annual yearly package and we have an unprecedented thousand dollars off our lifetime package and we are raising prices going into the new year. So if you want to take advantage of these discounts, they are only good and only available right now until December 31st. Take advantage, we will definitely, definitely be raising prices soon. Good morning MIC. Sam with a live trading video here. Got my two watches here, T-Con ABEO. Right as the market is about to open. So I'm hoping for a pop on this T-Con into hopefully 330s and it doesn't look like it. So I had a line of 310 but I didn't take it. I wanted ABEO as well into 350 so hopefully we can get a pop on that. I think once this breaks three this T-Con should be just game over but there's not too much meat, that's why I want to wait for a pop. But yeah I think there it is. I'm sure it's going to slam but I don't know, we'll see. There's not any pop. I'm going to look to short. Actually I want to slam 305 right there. We'll see. I'm just slam some because if this was strong in my opinion it would have already had the bounce since it didn't put in the bounce right now it's just consolidating so we'll see.  That was a watch as well. Missed that. Shit I just went to slam at three and I just missed.  All right so there we actually kind of snap back on volume. There's probably some early shorts covering. I'm just going to get like a quick just 250 shares at 95. So the support is around this 86. See if we can get below 86 and that's sort of uh is it 86? Yeah 86 and then that's sort of the confirmation again and then I'll look to you know short another pop hopefully up to three and there it is second. Yeah so I mean it could potentially go red but you know I'm just looking to to just lock in my gains now. I didn't get you know enough size I just it's not like a full like meat play for me so you know we slammed what we could and now we have confirmation that we can short pops. So now it's sort of stalling at this support so I'm going to take it off at 85, 500 shares. Oh wow we got eaten. So here it's rejecting the 90s level. We'll see here over three might be a little a little more interesting because I think this is just a heavily shorted player right now. I feel like if we can get over three we might be able to get some sort of push but I'm hoping I can fill right now at 89 some it's just it's kind of weird. I feel like I'm trading like a 10 cent range right now and so I'm just you know like I want more size but I'm trying to be a little smarter and get it like a couple cents higher but you know we're just waiting here I'm getting a little ad right here and then hopefully you know the next leg down when we crack low of day then I'll be looking to take it off you know I guess the line would be right here the low 70s that's what I would use and yeah just something like that into there. I'm not I don't think I'll hold a piece for red because I like to nail and bail before zombie hour so we'll see the bid just dropped so let me see tight big spread here got my coffee we're set so now we wait you know we didn't get enough size at all but you can't complain because in 10 minutes made almost 300 bucks so you know why even complain about that. So let's see here here's another low of day test oh I didn't get filled wow I had an 89 whatever I could probably should I chase that for like an extra cent but see that's sort of the that's like something I like hate myself for at times when I don't you know I'm like oh it's one cent and like you know I'm sitting here wanting more size but then I don't get filled based off one cent rather than just like slamming at 88 I think that's uh that's just kind of dumb with me but right here I'm just gonna take off another half at 79 just because um it's just sort of stalling here at low of day and then you know we'll keep this for the break so there's a new low of day see holy moly there's tons of bids so it's just you know for me if I see tons of bids like that and it's sort of chilling out low of day I just you know I'll take some off it's just like why not it makes sense it's not like oh I'm gonna just wait and see what happens what if out of nowhere this rocket's up you know you gotta just take some profit locks them in so now I keep some left and now we wait now I can save this for you know the the let's say we get another huge wash we'll save it for that and then then we can wait for a pop and then you know when zombie hour comes we'll avoid see this LXRX the difference again like I said this one's a very difficult one right now I was just slowly grinding like that up and just chilling around red to green so I mean who knows so now we wait hey traders this is Tosh I go by T Bradley 90 in the my investing club chat just wanted to reach out and say if you have any questions about MIC joining MIC maybe you're a member already you have three ways to contact myself personally and through MIC you can hit our social media you can hit me through pms in chat or you can contact us through my email at Tosh at myinvestingclub.com that's TOSH at myinvestingclub.com I will get back to you in a timely manner and I'm saying this because I'm here to help and I don't want anybody to be afraid to reach out and ask any question that they have we are here for you guys all right see you guys


Right, so last lecture, I think Matt covered two-phase locking. And two-phase locking is a mechanism that the database can use to essentially generate serializable schedules at runtime. And it relies on locks to be able to do that. Today we're gonna be talking about a collection of protocols that don't rely on locks, but instead rely on timestamps. At a high level, maybe a good way to think about this is that two-phase locking assumes that there's gonna be a lot of contention inside of the transactions that are executing inside in the database, right? So if there's a lot of contention, then it's obviously advantageous to be defensive and take a lot of locks. So anytime you wanna read or write into a database object, you acquire these locks. So in that sense, it's quite pessimistic. On the other hand, you can view timestamp ordering based techniques as more optimistic, right? You allow the database to operate and read and write data without actually acquiring locks. And at the end of the day, you're able to correctly reconcile the correct serializable schedule at the end of the day. And we'll talk about how this is actually done inside of the database. There's actually gonna be two timestamp ordering protocols we're gonna talk about in this lecture. One of them is actually called timestamp ordering or basic timestamp ordering. And another one is gonna be called the optimistic concurrency control. So it's a little bit confusing because they're both optimistic and the both timestamp ordering. This is just the nomenclature that the community has come up with. All right, so let's get started. The basic idea for these timestamp based protocols is that it's a mechanism that the database can use to assign numeric values to timestamps that predefined the commit order of these transactions. You can assume that there's gonna be a new function here called TS that, given a transaction, gives you the timestamp for that transaction. And so, what the database tries to guarantee is that if a transaction TI has a timestamp that's less than the transaction TJ, then in the serial schedule, it's as if TI had occurred before TJ inside of the database, okay? So how is this done? Like what do these timestamps look like? The timestamps are sort of unique fixed numeric values and they have a couple of interesting characteristics that the database has to maintain. The first one is that these timestamps have to be monotonically increasing, okay? So they have to always go forward in time and increase in time. The second thing is that they have to be unique values, right? So you can never have two transactions have the same timestamp because of this monotonically increasing characteristic. So again, assume that the database now has this new function, this TS function that's able to take a transaction ID and return to you the timestamp for that transaction. And these different timestamp protocols have different mechanisms and time points at which they actually assign these timestamps to the transactions. An important characteristic is that these timestamps don't necessarily have to correspond to the wall clock time because they could be assigned to the transaction at any point during its execution, not necessarily when it enters the system, not even necessarily when it's about to commit, right? So different protocols have different mechanisms by which and time points at which they actually assign timestamps to transactions. There's a few different ways on how you actually source a timestamp for a transaction, okay? And there's a few listed here. The simplest thing you could do is just ask the CPU, okay, what is the current time, right? Because time is always increasing, you could assume that this kind of makes sense, right? But there's a few drawbacks. Can anybody think about a few drawbacks for using wall clock time or real time as a timestamp? Yeah? You are not sure that the computer's time is actually correct? So that doesn't really matter. As long as you're going to the same computer, and as long as the time is monotonically increasing, then you should be okay. What if I have student data? Right, so that's a good point, right? So if you have distributed database, then it's difficult to keep these time points in sync. What's another problem with using wall clock time? It's not monotonically increasing, you can turn back the clock. You can turn back the clock. When would you actually turn back the clock? Maybe because of the TPU time synchronization and your computer is running faster than the server. Sure, yeah, so there could be some skew in the actual granularity, which you track time. Is there another possible drawback? Yeah. You have to keep all of the timestamp, rather than just like say like in event one, event one, event two, event three. You don't really need to keep track of how we're keeping track of that data you might not see. So you don't actually have to keep duration of time, you just need like one point. Like this is time point one, time point two, and it's increasing. So it's not necessarily by duration, it's just about a point in time. Okay, so a clue is that it's gonna happen this weekend. Yeah, exactly. Yeah, so daylight same, right? So it could be the case that you're operating on the weekend and then at random point, your clock goes back an hour and your timestamps are pretty much screwed, okay? Another option is actually to use these logical counters, right? So you can think of having just a register in the CPU dedicated to having a monotonically increasing 32-bit, 64-bit value. Are there any drawbacks or potential downfalls for this approach? Yeah. Yeah, so the distribution aspect is still an important factor. But assume that there's one counter for the CPU and it's really fast to increment it without requiring locks. Like you can do an atomic addition or something like that. Are there any problems with using this logical counter? So I said specifically 32-bits or 64-bits. What happens if you run out of 32-bit values? Then you saturate your addition and you roll back, right? So your counter is now going backwards in time. So that's one of the problems with this approach. So most systems actually use this hybrid approach, which is like a physiological thing, it sort of matches both the physical counter and a logical counter to make sure that everything sort of works out. Can you re-explain the problem with the system clock? So the system clock, one problem is you have daylight savings times, right? So at a point in time when daylight savings occurs, your time moves back an hour. So now your time is not monotonically increasing, it's not going back in time, okay? Right, so just to give you an idea of what the agenda is going to be today. So we're going to talk about something called the basic timestamp ordering protocol, then we're going to talk about optimistic concurrency protocol, which is also a timestamp-based protocol. And then we're going to talk about a partition-based timestamp ordering protocol, which alleviates some of the bottlenecks that regular timestamp ordering protocols have, and then we're going to talk about isolation levels, okay? So let's get started. So with these timestamp ordering schemes, the general idea is that you want the transactions to proceed in the system, reading and writing objects without actually acquiring locks, okay? To make this possible, you have to add some extra metadata to all of the database objects to make this possible. Specifically, you have to add two extra timestamps to every single tuple in the system. You have to add a read timestamp, which represents the timestamp of the transaction, the most recent transaction that read this item, and a write timestamp, which is the timestamp of the most recent transaction that wrote into this tuple in the system. And then as a transaction is going through its operations, it's going to make sure that it can actually read this tuple by leveraging the timestamps that are associated with this tuple, okay? And I'll talk about how this is done. So for reads, there's an invariant that you have to make sure before you're actually allowed to read a value from the database system. You have to ensure that the timestamp, so you read your own timestamp for this transaction TI, you have to make sure that it's less than the right timestamp for this tuple in the system, okay? Does that make sense? What does that mean? That means that's essentially making sure that there's no other transaction that's written into the system. Yeah, there's no other transaction in the system that's wrote into this tuple that should have read your, you're not reading a value of the tuple from the future, right? So there's a transaction in the future that's overwritten the database value that you should now be reading. That's essentially, that's a problem and when this happens, you essentially have to abort and when you abort, you have to make sure that you start with a newer time stamp than the one that you had when you initially began the transaction. Does everybody sort of understand why you need to assign a newer time stamp? What would happen if you had the same timestamp you had before? Exactly, you'd run into the same problem, right? So that's because you have to ensure timestamps are monotonically increasing, you have to get a new timestamp to avoid this problem. Yeah? Do you ever run into an issue if it was your timestamp that was last, like you double tried to double write to the same address and the same timestamp as your current timestamp also? So if your timestamp is the same as a write timestamp, what does that mean? That means that you wrote to it. Exactly, you can read it, you can read it, right? That should be, repeatable reads, that's perfectly fine. Yep. When we talk about the time of the transaction, is it when you start the transaction that doesn't matter? So in this scheme, the timestamps are assigned when you begin the transaction. Okay, so if this invariant isn't validated, you essentially have to abort. But on the other hand, if you're actually allowed to perform the read, then you modify the read timestamp for this tuple to take the maximum of whatever the read timestamp is right now and what your own timestamp is. Does anybody know why you have to take the maximum? Okay, timestamps have to be monotonically increasing, right? You could have a transaction that's newer than you, update the read timestamp, but you can't set back the timestamp back to what you were because you're older, right? Timestamps have to be monotonically increasing. So you have to take the maximum of whatever it is at this point in time and when you read it, and what your own timestamp is. This is important, okay? So once you've updated the timestamp, you now have to make a copy of this tuple into some local private workspace that's only visible to you so that you can ensure that you get repeatable reads. So assume that there's some tuple that you want to read, right? And the write timestamp is from a transaction that's newer than you, that's in the future, right? You shouldn't be able to read that value, right? You should be reading the value that existed before it wrote, before the new transaction wrote it. So that's why it invalidates. You're abhorrent regarding you are essentially reading that value in the future. You have, yeah, because you now appear in a different order in the serial order, right? You should, because your timestamp is newer than the one that wrote to it before, you logically appear after this transaction in the serial order. Yeah, go ahead. So this is not, I don't think it's covered in the book, but you have to make sure that you have to make a local copy so that you can issue repeatable reads. So you can imagine that another transaction comes in and updates the system but you have to be able to read the same value that you read initially. Right? But if you allow another transaction to update the value here, then you would invalidate this invariant at top, and you wouldn't be able to read it. But you actually should be able to read it, right? Because you read it and it transactionally consistent state. It's maybe like similar objects, maybe the same objects. I'm gonna have the problem where you restart it every time, but then you're gonna get the same problem. Yeah, that's a very good point. I think you're alluding to the fact that there could be starvation where you have consistently consistent imports. That's a drawback of this approach, and we'll sort of get to that later in the presentation. Okay, so this is just for reads. You have a similar story for writes. Okay, so if your time stamp is less than the read time stamp of the object that you're trying to write into, that means it's a newer transaction that read a stale value, a value that should have been coming from you as a transaction but is not anymore. So that's a violation of the of this time stamp ordering protocol. Similarly, if you have a, if your time stamp is less than the right time stamp of another, of the object, then again there's a newer transaction that essentially overrode your value. And again, that's a violation. And the idea is that if either of these conditions are true, you have to abort and again start with a newer time stamp value and begin the entire process again. So if on the other hand, this is a valid write, then you have to update the write time stamp to the tuple and you're essentially done. You have to also make a local copy here because in order to support repeatable reads, you'll read your local copy instead of going back to the, into the databases global state. Okay, so let's walk through an example. Hopefully this will clear things up a little bit. So we have two transactions here and just assume that you can only execute one transaction, one operation at a time. So you can assume single core, single thread. And in this database, we now have annotated all of the, the tuples we have. All of the objects here with the read time stamp and a write time stamp. Okay, so let's get started. So we have T1 and T2. When they enter the system, they're assigned a time stamp. Assume that T1 is assigned a time stamp of one and T2 is assigned a time stamp of two, right? Pretty simple. Then you do the read. So T1 does a read of B. You look at the right time stamp for B, it's zero, one is greater than zero. So you update the read time stamp to one. Then we do a context switch into transaction two. And T2 now wants to do a read of B. You look at the right time stamp and you're good to go. So you update the read time stamp to take the maximum of what it was, which is one. And the new time stamp, two, and you get two. All right. Now you do a write. So T2 wants to do a write of B. You look at the write time stamp and the read time stamp. You're greater than both. So you update the write time stamp of B to two, okay? Now you do a context switch back into T1. T1 wants to do a read of A. It looks at the write time stamp of A. One is greater than zero. So you update the read time stamp to be the maximum of zero, one. And you're good to go. Sorry. Yeah. You update the read time stamp to one. Now you come back over to transaction two. And two wants to do a read of A. You look at the write time stamp of A. Two is greater than zero. You update the read time stamp to two now. And then finally, T2 wants to do a read of A. So it looks at both the read time stamp and the write time stamp of A. It's greater than both of them. So the write is valid. And yeah, so no violations exist, no violations exist. So both transactions are safe and you can commit both of them. All right. Is this clear? Okay, good. So let's walk through another example. So it's the same setup here. All the initial time stamps are zero. T1 and T2 enter the system. T1 gets time stamp one. T2 gets time stamp two, all right? So in this scenario, T1 wants to do a read. It's a good read, so it updates the read time stamp. Do a context switch. And now T2 wants to do a write of A. It checks the write time stamp and the read time stamp. It's valid, so it updates the write time stamp to two. T1 now is trying to do a write of A. So it checks the write time stamp and the read time stamp. It's no longer valid because you have the time stamp of one, which is one, is less than the write time stamp of A, which is two. This is a violation. So T1 actually can commit. It has to abort. Is that clear? You can think about this as like in the serial order because T1 has time stamp one and T2 has time stamp two. T1 should appear before T1 in the serial order.  Okay. Sorry. So there's actually an optimization that we can make here to avoid aborting in the specific scenario, right? You can think about it as in physical time, what's happening, right? T2 is writing to something, but then it's being overwritten by T1. So do we really need this write? I think the observation is you actually don't need it. What you could have is, because we're maintaining a local, every transaction is maintaining a local copy of the tuples, this write here can essentially be ignored by the system, right? Because externally, this write is what's valid. And as long as this write is externally valid, then you don't actually need this one externally. Within the transaction you still need this write because you have to be able to read your own writes. So this observation leads to an optimization that you can apply in these time stamp based systems called the Thomas write rule. And the idea is that if you're trying to write into an object X, as before, if your time stamp is less than the read time stamp for that object, you still have to abort and start with a new time stamp. But if the time stamp is less than the write time stamp of the object, which means there's a new transaction that wrote into this object, you can actually just ignore the write altogether. You have a local copy of the write that you can now read, but externally it's okay to ignore this write. We have to update the local copy, right? Yeah, yeah. Yes. So this write is only important to T1, right? So it's not, it doesn't really, I don't actually have to propagate it back to the database because it's gonna be overwritten by this write because in the serial order, this happens first and then this happens, okay? Because this has a transaction, a time stamp of one, this has a time stamp of two. Yeah, so this optimization, and it's actually quite useful in this specific scenario, it allows you to have the, actually commit this schedule. So this is the same example as before. T1 begins, write reads A, updates the read time stamp. T2 begins, does a write. Now we recognize that this write should normally be invalid. We actually, but by applying the Thomas write rule, we don't actually update the write time stamp or the value A, but we just maintain this local copy, we ignore it and we allow T1 to continue. All subsequent reads for this read, all subsequent reads of A in times in transaction one occur in the local copy with this value, okay? So we won't now check the conditional, right? Yeah, yeah, so that's essentially basic time stamp ordering. Like two phase locking, it's a mechanism for the database to generate conflicts serializable schedules as long as you don't apply this Thomas write rule, okay? It does, you can prevent deadlocks altogether, because as you're similar to how two phase locking works, for every operation you're performing on the database, you're making sure that this is a valid operation. It's sort of like deadlock prevention, right?  Here, you're incrementally checking for every operation, whether it's valid or not based on these timestamps and then aborting eagerly as eager as possible, okay? One drawback here, which I think one of the students led to is you could have the possibility of starvation, right? You can think of a long transaction that's been running for a long time and then you have these short transactions that are performing that exist for a very short period of time, update a few tuples and then commit and leave. These are essentially gonna invalidate all of the old transactions causing conflicts, causing cyclical aborts, okay? So another thing that we should talk about here is these timestamp aborting protocols, they allow, they permit schedules that are not recoverable, okay? So what is a recoverable schedule? So a schedule is recoverable if a transaction only commits all the previous transactions that it relied on data from also have committed. You can think of this as like a cascading abort, right? You wanna make sure that if you read a value from it that's updated by another transaction, that that transaction commits before you commit. Basic timestamp ordering does not guarantee this for you. Okay, so I wanna talk about how this specific recovery, the specific characteristics is violated by basic timestamp ordering. So imagine we have the same set up here. We have two transactions, T1 and T2. T1 has timestamp one, T2 has timestamp two. So T1 does a write of A, T2 does a read of A and then a write of B. So in the serial order, T1 occurs first and T2 occurs second. So this read can now read this right and that's okay. It does some write of B, which is okay and commits, right? So T2 has committed at this point. But let's say later on in the system, this transaction has aborted. The problem is that we've now notified the client, we've notified externally to the world that this transaction has committed. But it read a value from a transaction that aborted, right? So this is actually invalid and it's not a recoverable schedule because when the system comes back, we have to recognize that this is aborted and that we should not apply these writes, okay? So this is not a recoverable schedule but it is permitted by the basic timestamp order and concurrency protocol. Yeah, so T1 aborts after T2 is committed and this violates the recoverable schedule requirement. Okay, so I think a lot of people have sort of picked up on this, but this basic timestamp ordering, that the protocol has a lot of overhead, right? So every time you do a write or read, you need to now copy it into your local workspace. So if you're updating or reading and writing billions of tuples, you have to make billions and billions of copies per transaction in a local memory space, right? And that's obviously a lot of overhead. Another thing that again was picked up by one of the students is that you could have starvation by from long running transactions, by short running transactions that quickly update one or two tuples and then require the long running transaction to abort and restart. So what can we do? If you think about it, right? So two phase locking and this basic timestamp ordering protocol that I just talked about, they're also somewhat pessimistic, right? So in two phase locking, as soon as you read and write a value from the database, you have to acquire some lock to protect yourself from other transactions in the system. With basic timestamp ordering, you're kind of doing the same thing, right? Every time you want to read and write a tuple, you have to make sure that the timestamps align just right so that you can perform the operation that you want to perform, right? So they're both assuming that there's a lot of contention in the system and try to prevent something wrong from happening. But what if you make a different assumption? What if you assume that there's not going to be a lot of contention in the system? What different types of optimizations can you apply assuming that transactions are essentially very short lived and are essentially conflict free, right? Can you be even more optimistic than the stuff that we've talked about so far? And we'll talk about one example, one concurrency protocol that makes this assumption and applies a lot of different types of optimizations, okay? And it's called, as the name suggests, optimistic concurrency control. So it takes a very optimistic view of how the transactions run in the system. So OCC, optimistic concurrency control, was written here at CMU by HD Kung. This, he's no longer a professor here, I think he's at Harvard, but it's pretty cool that one of the premier concurrency control protocols was actually written here at CMU, okay? Oops, the idea is, as in the basics timestamp recording protocol, every operation you perform, what you do is you first make a local copy of that data into a local thread, local private workspace, okay? Anytime you wanna read a copy, anytime you wanna read an element from the database, you first make a copy from it and then you're good to go. If you wanna make an update to it, you first make a copy of it into your local workspace and then you apply the update to your local copy, okay? You don't perform an in-place update anymore, all right? Then, once all of this work is done and you're ready to commit, you have to essentially make sure you have to validate that all the changes you make are transactionally consistent with the rest of the transactions that are running in the system concurrently with you, okay? And I'll talk about how this is done specifically in the workspace, in the following slides, sorry. So after this validation step, after the database has ensured that, hey, listen, your transaction is good to go, we have to now install all the changes that are in your private workspace into the global database system and we have to do this atomically, okay? And again, I'll talk about how this is done in the system. Okay, so the way that OCC works is that it's split up into three phases. The first phase is called the read phase, then you have the validation phase, which is essentially gonna validate that this transaction is actually still valid and doesn't conflict with anything else and once the validation phase is done, then you actually have to install your changes from your private workspace into the global database, all right? So the read phase is a bit of a misnomer, right? You're actually allowed to do both reading and writing in it, so I didn't wanna make sure that that gets across. I actually don't even like the phrase read phase, I actually prefer work phase where you're doing the actual work for the transaction. Okay, so in the work phase, you're making your reads and writes, you're updating values, you're reading values, all in a private workspace. In the validation phase, when the transaction is ready to commit, the database does a bunch of sanity checks to make sure that this is a valid transaction and then in the write phase, you atomically install all your changes into the global database. Okay, so let's just quickly walk through an example of how this is gonna work. Okay, so the first thing is that we have the same database we had before, but we've removed the read timestamp now, we just have a write timestamp. The second thing is that we've now demarcated the boundaries for all the phases. We've really just done this for illustration. The transaction is not gonna specifically say, hey, I wanna start my read phase, I'm gonna start my validate phase, and then the commit phase, it's gonna be handled for you by the database system itself, much like how the two-phase locking protocol is implemented for you by the database, not by the transaction, right? The transaction's just doing a bunch of reads and writes. Okay, so another thing that I wanna point out is that unlike basic timestamp ordering, the timestamps aren't necessarily assigned when the transaction entered the system. Okay, they're actually deferred to a later point in time, and we'll get into how that's done. Okay, so we're ready to get started. We begin transaction T1. It now wants to do a read of A, so it constructs a private workspace that is essentially somewhat of a copy of the database. Upon read, it's gonna read, or make a copy of A into its private workspace along with the right timestamp for whatever it read from the database system. Now T2 begins, and it begins its read phase. When it begins the read phase, it has to construct this private workspace for transaction T2. It does a read of A into its private workspace along with the right timestamp, and then we're good to go. So now we get to the validation phase. So this is essentially T2 saying to the database, hey, listen, I'm ready to commit. What it does is the database will now enter the validation phase for T2. It's at this point that the timestamp is assigned to the transaction, okay? So far, this transaction doesn't yet have a timestamp. You can assume that its timestamp is infinity. Here, when T2 enters the validation phase, it gets a timestamp of one, right? So what does it do? It now, it doesn't have to do any sort of validation because there's nothing to really validate. It's a read-only transaction. So it begins the right, it falls into the right phase. There's nothing to write, and then it commits, and everything is sort of done. Okay, that's a pretty simple example. Now we do a context switch back into T1. T1 now wants to do a write. So it makes a modification to its local copy and it assigns a timestamp of infinity. Okay, why does a timestamp have to be infinity? Does this transaction have a timestamp yet? It doesn't have a timestamp, right? Because it has an entered validation. You only get a timestamp when you enter validation. So if it doesn't have a timestamp, then it doesn't know what its timestamp is gonna be, so it assumes infinity, right? And it'll fill this in when it begins the validation phase, which is here. So it now begins the validation phase. It gets a timestamp assigned to it, too. And then there's no other concurrent transactions running in the system, so the validation phase completes. And it now has to write its local copy, all of its local changes into the global database space. When it does this copy, it has to update the right timestamp for this tuple A to the timestamp that it was assigned when it began validation, so two. So it writes the right timestamp of two here. Okay, this is a pretty simple example. It's like a happy path example of how transactions work. Okay, so the work phase is sort of simple, right? Anytime you wanna read and write a value, you make a copy of it into your local workspace and then you modify the local workspace alone. Once you're done the work phase, you would now begin the validation phase. The validation phase is where the database ensures that the schedule that it can generate is serializable, right, it's conflict serializable. The way that it does this is that for every transaction, it has to make sure that the read-write set, right? So the set of things that it has modified doesn't conflict, doesn't have a read-write conflict or a write-write conflict with all other concurrent transactions in the system, right? And there's a mechanism for how to do this. There's actually a couple of different mechanisms. All these slides are a little bit out of order. And the way that you, so the way that the database can ensure that these transactions don't, or like the sets are properly serializable, is that it needs to have a global view of all active transactions running in the system. If you have a global view of all transactions running in the system, you now have a global view of all of the modifications every transaction has made in the system, okay? And then you use these read-write sets as a mechanism to determine the ordering of the transactions in the system. So I think one of the things that we wanna try to get across here to simplify the entire protocol is that this validation and writing happens serially, serially. So the entire system, you can think about it as there's a giant latch over the validation phase, quote unquote, validation phase to ensure that there's only one transaction performing validation at a time. And this will simplify some of the protocols, we're gonna simplify some of the details we're talking about in the protocol a little bit later on. So yeah, so in the read phase, as I mentioned before, whenever you're trying to read and write a value, you make a local copy and you only update that local copy to ensure repeatable reads. And then in the validation phase is when you get a timestamp and then you use this timestamp to look at all other concurrent transactions in the system to make sure that you don't intersect like your read and write sets don't intersect to make sure that you have a correct serial order. So you look at your timestamp for TI, you find all other transactions in the system that are younger than you, that are newer than you and you have to make sure that a set of conditions holds. I mean, the fact that we're using newer transactions isn't necessarily required, you could also look at older transactions, right? There's no reason why we're specifically looking at younger transactions, but it simplifies, it makes things a little bit simpler. And I'll talk about another approach that we can use that's slightly different than this one. So when you're ready to validate, you essentially invoke the commit and then the database performs a validation phase. So it finds, because it has a global view of all the transactions in the system, it can find all newer transactions and all older transactions and make sure that everything sort of fits together. And there's two types of validations that you can perform. You can perform forward validation or backwards validation, right? So what is the difference between these two types of validation techniques? So in backwards validation, what you're looking at is when a transaction is ready to commit, let's assume that transaction T2 is ready to commit, you look at all the older transactions in the system. Okay, so T2 is ready to commit, its commit point is here and you're doing backwards validation. You have to find all older transactions. So transactions whose timestamps are less than this one and perform a validation, right? So we call this the scope of things that we have to look at a validation scope. So this is the validation scope for T2 if you're doing backwards validation because T1 and T2 are running concurrently and T1 committed before T2. So T1 is older than T2, all right? Because it could be the case that T1 made an update to something that should have been read by T2, but we didn't because T1's changes are made to a private copy, all right? So it could be the case that we read something from the database system that we should have been reading from T1, but we actually read from the main database because the T1 is making private changes to its own space. So we have to make sure that this doesn't happen and if it does, we have to actually abort T1. So this is backwards validation. We're looking backwards. So if there is a conflict, we abort T2? Correct, yeah, because this is already committed, right? At this point, we can't do anything about T1, okay? Similarly, instead of going backwards, you could also look forwards. So again, we're trying to do the validation for T2. We find all concurrently running transactions that have not committed yet and we do a validation against those. So in this specific scenario, T3 is concurrently running and we have to make sure that this is transactionally safe because it could be the case that I made an update. So T2 made an update into its local private space but because it occurs before T3 in the serial order, this one has read a stale value from the database. It should have read something that I modified, like maybe I modified it here and it hasn't read it here, but it actually read a stale value. And if that happens, I have to abort myself. Okay, so these are just two techniques, two mechanisms in which we perform the validation. What's really important here is that all transactions perform this validation in the same direction. You can't have T1 performing forward validation and T2 performing backwards validation because that's going to mess up the entire system. Yeah? So like if you're doing forward validation and T2 completed its validation stage, right? But what happened was after that, somehow like something happened and it aborted. So now I'm thinking about T2, but T3 has read something that T2 has written. So now somebody needs to abort T3 also, right? So if the validation completes, then you're essentially committed. You're ready to write your changes out. But like just when you've completed validation, something happened and you abort it. Like something can happen in the database, right? Even like the system goes down? Like so you're saying after validation completes, nothing can happen that can make T2 work? No, yeah, because if validation is successful, that the database is saying that this is a valid transaction. It doesn't conflict with anything else. So it should now be installed into the system, all right? So okay, so for the rest of this lecture, let's just assume that we're always doing forward validation.  Okay, so there's a couple of different scenarios that we have to cover. Okay, the first scenario is that if you find a transaction Tj, where all your phases, your read, sorry, your work, your validation and your write steps happened before anything that Tj has done. This is sort of like the simple happy path case. So this is an example. You have T1 and T2, T1 completes all of its steps before T2 has done anything. Okay, so this is a really simple example. You could essentially collapse this into one and now you have a serial execution. So you don't really have to do anything all that interesting here. This is sort of given to you naturally. The second scenario that we have to handle is that if T1 completes before Tj, sorry, Ti completes before Tj begins its write phase, okay? And we have to make sure in this scenario that the stuff that we write, the write set in our transaction doesn't intersect with the read set of the other transaction. So the other transaction hasn't read anything that we've written. Okay, why is this important? So let's walk through an example. So in this scenario, we have two transactions. T1 is reading and writing A. T2 is reading A and doing nothing else. So this is the state of the database. So T1 has read A and written to it, assuming that it's writing the same value one to three and its timestamp is infinity. T2 has read A, so it has a timestamp of zero there and it has a local copy in its private workspace. And then you want to perform the validation here. So T1 has to abort because its read set, so it has a lower timestamp than T2 because it begins validation first. So its write set intersects with the read set here. So that violates the invariant that we had before, so we have to abort this transaction. Okay, in the serial order, T1 has to begin before T2, but T2 has read a stale value, so we have to abort. I think it's a pretty simple example. But now let's slightly tweak it and now we'll have T2 begin validation before T1. So in the serial order, T2 happens before T1. What's gonna happen in this case, right? So T1 reads A, begins validation, it doesn't have a write set, so it doesn't have anything to intersect with this transaction, so it commits. T2 does the same thing. Its write set doesn't intersect with the read set. Doesn't intersect with any other concurrent transaction because this one's already validated. So nothing happens, right? So in the serial order, T2 happens before T1, it reads the value of A that initially existed before. This transaction is gonna read the value of A there, make a local copy, write to it, and everything's okay. Questions, yes? In this case, it's going to be a good transaction to not read a stale value. So in this scenario, because T2 begins validation first, it appears first in the serial order. Yeah. So in this case, it's why T1 has to abort. So T1 has to abort because in the serial order what should have happened is that T2, because it begins validation first, it's the first to recognize that there's something wrong. So it recognizes something's wrong as soon as it begins the validation because it gets assigned a timestamp, it sees a concurrent transaction that's read a stale value, so it aborts. Then how much does T2 go to validate? So when T2 goes to validate, T1 is no longer a valid transaction, so it won't see any concurrent transactions. There's nothing to intersect with, and also it's a read-only transaction, so there's nothing to intersect with. There is a very question, maybe I forgot the trigger question. But what if the T2 read a new value after T1 writes it? Oh, maybe because T2 couldn't read the value that T1 would like to write. T2 couldn't read the value from T1. No, not until it stalls, it changes because it's a private thing. Yeah, yeah, question. So in this case, in the first example itself, it won't write timestamp or T1 gets updated to 1, and from that it will understand that T2's validate phase as not. Like it can't compare from infinity, right? When it starts the validation phase, then it gets a new timestamp, and then only it can get to no right number. Yeah, so when this T1 begins its validate phase, it'll get a timestamp, yeah, it'll get, I don't know, one or two or something. But this T2 doesn't have a write timestamp yet. Because it is zero, right? Yeah, I mean it's infinity. It doesn't have any timestamp because it hasn't begun validation yet. But its timestamp will be the value read from the data? No, no, no. It will be infinity when it writes? No, no, no, no, so the timestamp is assigned to the transaction. It doesn't assume that, it doesn't take whatever timestamp is from the tuple. Yeah, so that's just a local copy. Yeah, I'm talking about the local copy. Oh, okay, yeah. The local copy will have zero, and it will have infinity only when you write on it, right? Yeah. Until you start validate. Yeah. This one will have one when you start the validate, and it will see that that guy has zero, so it has not started the validate because its timestamp is the same as the database one. Are you saying if T2 performs a write to this object A, it'll get a, it'll modify the write timestamp of its local copy to infinity? Yeah, so it is checking that, right? Yeah. Since it is same as the database one, so it's getting to know that neither it has written to it and neither the validate phase has started. The validation phase has started, and then this timestamp would be like two or something else, not the one that it writes. Yeah, so if it makes a write, it'll get a local time, it'll get a timestamp at validation, and it'll update the write timestamp there, if there's no conflicts. Yeah. In our second example, I saw that after our validate phase, what you do we did not immediately write. Does that make a difference? If the... Like a write phase of transaction two is not going to get to be after the validate phase, shouldn't it be writing when it will be after the validate phase? No, no, no. You have to have this write to be atomic, so you write all your changes back into the database in this phase. But then after we validate it for T2, we let T1 write first. That's just because of the schedule that we have here. So we have the, you can think of it as like we begin the validation, we finish, and then we do a context switch here, and now we begin the validation in the write phase. All right, so this is the second example. There's still one more to go. In this one, the transaction, you have to ensure that the transaction TI completes its read phase before transaction TJ begins its read phase. So you have to ensure that the write set of my transaction doesn't intersect with the read set and the write set of the transactions that fall into this category where the read phases are overlapping. And this is another example of how we can go through this. So let's see. In this scenario, T1 is reading and writing A. Oops. T2 is reading B and reading A. T1 begins its validation phase. So it gets a timestamp of one. And now I can commit it because my write set doesn't intersect with the read set of transaction T2 at this point in time. So I can install my changes back into the database. I update A with the value 456, and I set my write timestamp to one, which is the timestamp that I was assigned at validation phase. Then when we come back down into, we do a context switch back into T2. T2 does a read of B. Sorry, a read of A. And now it can go back to the main, it goes to the main database and does a local copy of the updated value of A made by T1. And then it can validate and write successfully because there are no concurrent transactions. Good? Yeah. I'm a bit confused about the time sense. Could you explain when will we put zero or infinity or one for the time sense? Let's go back to this example. So when you want to perform a write, you make a local copy of the database object into your local private workspace, and then that's when you set the timestamp to infinity. You set it to infinity because you don't know what your timestamp is going to be because you haven't been assigned one yet. It's zero here, mainly for illustrative purposes. You can think about, there was some transaction with timestamp zero that bulk loaded all of these objects into the database. So that's why the write timestamps are zero. So when you read it, what happens when you read it? When you read it, you read whatever timestamp is associated with the object at that point. Yeah, so T2 does a read of A, does a validation, does a write, everything is good because there's no concurrent transactions. Yeah. Yeah, these are all forward validation. Yeah, correct. Yeah, you still need to rely on the same timestamps. Yeah, so that was essentially the, we've been kind of hand wavy on a couple of things on how you actually install the writes atomically and how you do the validations in a parallel way because in a real system, you have to do this parallel validation, but I think hopefully the main idea has gotten across. It's not too complicated. There are some, there's some trickeries here and there, but generally it's pretty intuitive. So there's a few observations that we should try to make. All of these timestamp ordering and optimistic concurrency protocols sort of work well when there's very little conflict, right? Because you allow the transactions to proceed without acquiring locks, without doing anything heavy weight at work time. And at the end, you do sort of a lightweight, semi lightweight validation to make sure that your transaction is still valid. So if you have very few, very few conflicts, even better if all your transactions are essentially just doing read-only work, and if the access disjoint sets of data, then these protocols work very well because they're actually not doing much work at all, aside from doing some local data copying, right? Another way to think about this is that if you have a very large workspace and very small transactions, and the probability of these transactions overlapping in the read and write sets is very low, in this specific scenario, these optimistic concurrency protocols work very well. On the other hand, in very highly contentious workloads, what ends up happening is that you have transactions consistently restarting, right? So they'll do a lot of work in their work phase, assuming that there is no, there is no contention, and only at the very end do they figure out, oh crap, all this work that I've done is kind of useless after we start, right? So you're kind of deferring a lot of the heavy lifting towards the end, assuming that there won't be a lot of heavy lifting, but in the contentious workload, there is heavy lifting because you essentially have to abort everything you've done. So really, I think the research sort of shows that in contentious workloads, both two-phase locking and these optimistic concurrency protocols generally don't work. They're sort of like almost equivalent. So in 2PL, you're essentially acquiring, there's a lot of contention on locks. So you have transactions waiting and these hot locks. Here you have transactions that are doing all their work, almost wasteful work, and then aborting at the very end. So neither really work for contentious workloads. But if your workload has very low contention, then in general, these optimistic protocols work better because they have no overhead, very minimal overhead aside from some local data copy. Whereas in the 2PL protocol, you actually have to acquire locks, even if there is no logical reason that you should be acquiring these locks. So the timestamps are assigned at validation. I think what you're describing is essentially basic timestamp ordering. So in basic timestamp ordering, you assign the timestamps when the transaction begins. In OCC, just the protocol dictates that you assign the timestamps at validation time because you want to defer the work of doing the actual checking to when you're ready to commit. Whereas basic timestamp ordering is saying, every operation I'm going to perform, I want to do a check to make sure that this is a valid operation. So just how the protocol works. You still need to make a local copy even if you're reading to ensure repeatable reads. So this slide is essentially just saying that for low contention workloads, these optimistic concurrency protocols work very well because they have very little overhead. In comparison to two-phase locking, which even if you have disjoint working sets between transactions, you still have to have transactions acquire locks. Whereas here, there's no locks at all. But here, when you are reading the values of the other tables, like the transaction one needs to check with the overlapping transactions table, then also it has to acquire some sort of lock, right? Nah, this guy, yeah. You're right. So you don't have to acquire a database of a lock. You still have to acquire latches. You still have to ensure the integrity of the data structure is valid, right? You can't just blindly overwrite stuff in memory because there could be concurrent access to these structures. So I think you're kind of hitting on the point that we will talk about it, I think in this slide. Yeah, so there is a little bit of overhead in OCC, right? Because you have to maintain local copies of everything that you want to read and write. So if you're updating a billion tuples, you have to make a billion copies. Every transaction has to make a billion copies. And so there's a lot of overhead here. The other thing is that the validation in the right phase is they were happening serially, right? The only one transaction can be validating at a time. In reality, you know, in real systems, you have parallel validation and parallel writing. But again, even those, in those scenarios, these phases become a big bottleneck. And lastly, because we're being optimistic, we're assuming that we can perform all of the work safely without being interrupted by other transactions. But in contentious workloads, that's not the case, right? That assumption isn't validated. In contentious workloads, we're doing all this work up front, and then we could find out later that we actually have to abort. So all of this work is wasted. We're being optimistic and we're being wrong about that optimism. So when a transaction commits, I think the student was pointing this out correctly, even if the transactions logically don't overlap with each other, you still have to make sure that you maintain the physical integrity of the data structure you're going to be looking at. So as part of the validation phase, you have to look at, oh, I have, you know, these other thousand transactions. I have to look inside the read and write sets in a consistent way. I make this consistent by acquiring latches, right? So this latch overhead can actually play a big role. Even if they're logically disjoint, physically, they're still contending on the same data structures, right? They're still contending on the read and write data sets, even though logically they're disconnected. Yes? Why do you have to do that? So when I'm doing my validation, right, I have one transaction and me, I'm ready to validate it. I have to go into his read and write transaction set to make sure that we don't intersect, right? But he could be modifying it because he's still running. He or she's still running, right? So I have to acquire a latch, read a consistent view of it, perform the intersection to make sure I'm okay. And he and this other transaction can modify that set while I'm reading it. But it's actually modifying in its local copy, right? But I'm reading the local copy. I'm reading that transaction's local copy of the working set. Why don't you just look at the table? Because the table doesn't have all of the updates that have been applied that this transaction has read and written to, right? The transaction has a local copy of reads and writes. So to see if this transaction has read a value that I'm writing to, I only know that by looking at his read and write set. I don't know that by looking at the table. So I have to look at the local working copies for all the other transactions as part of my validation. And in order to do that in a consistent way, I have to acquire latches. And these latches can have some overhead. Yeah. So to produce content on the latches, could you do some sort of filtering? I feel like you only, because each transaction will be only accessing a small number of things. Yeah, there's a lot of techniques that you can use to reduce the slash contention. But at the end of the day, even if you have a parallel setting, there is some overhead. So what if we take a slightly different view? What if we partition the entire database so that all of the stuff that one transaction has to work on is only within one transaction, and then I can remove all of my locks and latches altogether. Is that even possible? So it turns out that this is a valid technique and it's called partition-based timestamp ordering. The idea is that I want to split up my database into these horizontal partitions, right? And then I want to be able to use timestamps to order the transactions on a partition in serial order, right? So if I have transactions executing serially, then there's no reason, sorry, within a database, there's no reason to have locks and latches at all because there's no concurrent activity, right? If they're operating single threaded. I don't need locks, I don't need latches. And then it gets a little bit complicated if you have to access multiple of these database partitions, but if you're only accessing all the data within one partition, then it can be potentially really, really fast. And this is sort of what partition-based timestamp ordering is trying to achieve. So let's walk through an example. So imagine that I have this schema that represents some online store that I'm running. I have customers, orders, and the order items, the items in the order for an order. What I could potentially do is, because I have these foreign key references, I can store within one partition of the table a set of customers, all of their orders and all of the items for their orders by using this foreign key reference structure. So imagine that I have two databases now where I have customers one through 1001 and 1001 to 2000 in a separate database. And I want to, let's say, I want to update a customer's name, I want to add an order to one customer's order, right? What do I do? So a transaction, I have an application here and it begins a transaction. And let's say that it's trying to update customer one. It falls into this partition here. So, okay, it's missing something. So assume that in this line, there's an operation that says, get me the name of the customer whose ID is one. That's an operation that obviously falls into this partition because this customer belongs in this partition. And then it does commit. And it can safely do that because all of these transactions get queued up and operate in a single thread in this database. There's no concurrent activity at all. Similarly, I can have another application server that wants to update the customer 1004. That'll go here. And these two transactions are totally disjoint. They're operating on different customers. And that's one way that we get parallelism even though each database is operating single threaded. Okay, the finer grain that we can have these customers, we can store these database partitions, the more parallelism we can get. And that way, each individual transaction runs much faster because we don't have to acquire locks and latches. And we get parallelism by having more of these transactions running concurrently on disjoint sets of the data. Is that clear? All right. So this turns out to be a very popular protocol. You still have to assign transactions and ID, and then you queue them up by these IDs. And this type of partition-based protocol has been actually very, very, very successful. So Andy worked on this system called H-Tor, which is a commercial system that got commercialized into Volt-DB, and they're still using this type of partition-based timestamp ordering. Andy worked with someone called a professor called Dan Abadi who's at, I think, Maryland now, who did some initial work on a system called Calvin that's now been commercialized into Fauna that also uses something very similar to this. And there's a system called KDB, which is like a financial database, and they also use this technique. And it's actually pretty successful if your workload supports this type of partition-based operation. The way that you can view this is that every single database essentially has a giant lock or latch around it, and when a transaction is ready to commit, it acquires this latch, and it begins execution within the database fully single-threaded bare metal speed. And then as other transactions come up, they queue up on this latch, and they essentially get assigned a timestamp, and then as their timestamp gets ringed up, they begin execution into this database partition. Okay, yeah, so that's it. So for reads, the transactions can essentially read whatever they want right now safely without acquiring latches because the database system guarantees that there's no other transaction running in the system. This is great if you only want to read stuff within one database partition. It gets complicated when you want to try to read rows that exist across partitions. So in the application server we had before, let's say that you want to modify within one transaction customers from two different partitions, that becomes complicated because now I have to acquire the lock for one partition and acquire a lock for the other partition before I can do any sort of operation. And oftentimes it's not even possible to know a priori all of the partitions I have to touch. So some systems what they actually do is they'll run the system in sort of like a speculative or like reconnaissance mode to figure out all the partitions I need to access, and then roll back, acquire all the locks ahead of time, and then begin execution. Yeah, so that's essentially what this is talking about. If I have to access cross partitions, cross partition rows, I have to abort and restart and acquire the new locks, the new set of locks that I've discovered during execution. And this can be wasteful. So you have to be kind of careful about when you want to apply partition-based timestamp order. So in contrast to regular timestamp ordering and OCC, I can now apply all my updates in place. So in OCC and in basic timestamp ordering, I had a private workspace that I have to apply my updates so that I don't conflict with other transactions that are running concurrently that want to read the same stuff that I'm writing. But here, because the system guarantees that there's only one transaction running at a time, I can apply my updates in place. And of course I have some extra logic to ensure that when I abort I undo those changes, but I can do this without making a local copy. So I've reduced the data copying overhead that would normally exist in OCC systems. And in the read case, if I try to modify a tuple that exists in a different partition than what I'm writing on right now, I'll abort, restart, get a lock on both database systems or database partitions, and then begin my execution. Yeah. Why do you think that it's going to be just a single thread for each partition? It can happen that multiple, you know, it's like if we consider that as a separate database, we still would need to have the local copy, right? No, no, because every database has only one transaction execution thread. Every partition has one transaction execution thread. Right? That's sort of one reason why you want to do this, because by having only one thread, you don't have to copy, you don't have to have locks and latches. Yes? Won't this lead to a lock? I'm trying to have a lock here and trying to get a lock here and the other transition has a lock here and he wants to get a lock here and we both award then again the same thing happens, and we continue doing this. Yeah. So I think there are ways that you can remedy this, right? If you have a deterministic order that you acquire the locks, that's one way to alleviate this problem. But I think you're sort of alluding to the fact that you could have the case where you keep learning during execution that you're touching different partitions. So you do a bit of work, realize you have to acquire a lock for a partition that you don't have, abort, retry, get further in the execution, realize you have to acquire a different lock and a different partition, abort, and then restart.  There are only two transactions and they want to acquire two locks. Then if they are trying to acquire both the same lock and one for it, one for the other, they can't acquire each of the locks and they also can't do the transaction because they need to have both the locks before taking the transaction. So they both have to abort and they both will come back, both have taken one lock, both have to again abort. Yeah. So you solve that problem by having these transactions acquire the locks in a specific order in a deterministic order. So let's say you have partition A and B. You have T1, T2, trying to access A and B. They realize that they need different partitions and they restart the abort and now they all acquire A and they all acquire B.  All right. All right. So that's essentially partition-based time-stop ordering. This is sort of a visual illustration of what's going on. So you have two servers that are both trying to access some customer data in this first partition. They issue a begin request. They get queued up in this transaction queue. They get assigned timestamps. Assume that server one gets timestamps 100. Server two gets timestamp 101. Obviously, the database system will take the transaction with the lowest timestamp, in this case, the one from server one. It begins execution by acquiring a lock on this database partition. It finishes its execution.  It's getting the customer ID and it's updating this stuff. The animations are a little bit wonky, but then it does a commit. It's safe because nothing else is running at the same time. So now this partition can now move up. This request from server two up in the queue begin execution, acquire the lock, and then the whole cycle continues. All right. As we've sort of talked about a little bit, these systems obviously are not a silver bullet. They have some performance issues. So these systems are very fast if the database knows what partitions the transaction needs before even beginning execution. That's not really possible in sort of an interactive transaction protocol, right? But you can remedy this by having stored procedures. In stored procedures, you declare everything, you don't have to do round trips back and forth, and the database runs everything on the server side so it can determine much quicker all of the locks the system needs during execution. And if the transaction only touches one partition, then obviously it's going to be really fast, but if it has to touch multiple partitions, then you have to do some execution, abort, retry by acquiring more locks, and then continue execution again. So it becomes slower. But if your transaction only touches data within one partition, then you're essentially running at bare metal speed and it's single-threaded, right? There's no locks, no latches. The other drawback is that if you have this multi-partition setup, you could have some partitions that are essentially idle because you have one hot partition. Okay, so that was essentially partition-based time-stamp ordering. I'll try to get through this as fast as possible. So one of the assumptions that we've been making throughout this work is that as transactions execute, they don't really insert new data. They only modify data and they read data. So when you now add the requirement, the data can be inserted and updated and deleted and inserted during execution. It violates some of the assumptions that we've made in our protocols and we have to handle them. And specifically, it introduces an interesting problem that's called the phantom problem. So imagine that we have the same sequence of execution here, but now I'm using SQL statements instead of regular read and write operations and we have these two transactions, T1 and T2. We have this database here of people that have name and age and some status. So I have transaction T1 that's performing... that's getting the maximum... the oldest person whose status is lit, okay? So let's assume that it runs and it figures out that the maximum age is 72. And then we have this transaction T2 that's essentially going to insert into the same database with a new person whose age is 96 who also happens to be lit, right? And then we get back here. So it's the same T1 tries to re-execute the same query and it gets a different version. It gets a different result from this query. So it got 96 here and it got 72 here. This is clearly a problem, right? Can two-phase locking solve this? Assume tuple access. Who said no? Why do you say no? Because new tuple comes then you won't have a lock on that. Yeah, exactly. That's exactly right, right? You can only access locks on tuples that exist. So because there was a new transaction that inserted a new tuple I didn't even have something to acquire a lock on, right? And that's clearly a problem. So if I want to solve this, if I want to ensure serializability I have to ensure that I can ensure, I can ensure Rupito reads so I have to solve this fandom problem. Okay, so what if instead of acquiring locks on tuples I can acquire locks on abstract objects? What if I can acquire a lock on an expression status lit? Would that solve the problem? If I had a lock on all tuples that satisfied the condition status is equal to lit. Who says yes? Who says no? Who says they don't know? Okay, so the answer is yes. If you could have a powerful enough locking system that you could have a lock on an expression that says status is equal to lit, you can solve this problem. That would solve it for you, right? But the problem, and the term that we're talking about here is called predicate locking, is that it's very, very expensive to be able to do this. And in fact I don't think any systems actually do that type of really complex logic because it's very complex. Okay, I gave you one example of status is equal to lit, but what we're actually talking about is a multi-dimensional problem because you could have any arbitrary complex expression and you want to ensure that the expression you're evaluating doesn't intersect with this multi-dimensional space. So it's non-trivial to implement. So most systems don't do that. Yes? What's the hierarchy of locking themes of in the last lecture solved this problem? Yes, so you could acquire a table level lock or a page level lock. Yeah, so you could use these hierarchy locks, that's one way to definitely solve it. The other way to solve it is this predicate locking that I was talking about, which is more general purpose and there's another one called index locking. So if I have an index on the system, let's say I have an index on the status attribute, what I could do is take a lock on the slot in the index where status is equal to lit so that any new insertions have to go through the index and not make an update, they can't acquire that lock. So that's another way to solve it. If the status lit doesn't even exist in the index, what I have to do is acquire what's called a gap lock. So a gap in the index, I acquire a lock on that gap so that if another insertion comes in that tries to insert status is equal to lit in that space in the index, it's not allowed to do that. So that's essentially two ways to do it. Yeah, so this essentially goes back to the point that was made earlier. If you don't have an index and you don't have predicate locks, you could do it by locking every page or you could do it by locking the entire table or yeah, hierarchical locks. So the last way to solve this problem is to just by repeating the scans by the committing, sorry, before committing. So I think one of the most popular systems that does this is Hecaton, which is from Microsoft. So essentially every, before you commit, you have to make sure that everything you read before happens just before you commit to make sure you have consistent reads. I think we're out of time. The last section was weaker isolation levels. Maybe we'll cover that in the next lecture. All right, all right, that's it. Oh yeah, coming through with Michelle and crew. Two cent for the case. Give me St. I's crew. In the midst of broken bottles and crushed up can. Met the cows in the gym or I'll drive. He's with St. I's in my system. Crack another unblessed. Let's go get the next one. Then get over. The object is to stay sober. Lay on the sofa. Better hit down my sofa. I'll be tamed. Stressed out. Could never be sun. Rick and say jelly. Hit the deli for a port one. Naturally blessed, yes. My rap is like a laser beam. The thorns in the bushes. St. I's been like a team. Crack the bottle of the same eye. Sipping through those you don't realize. And drinking it only to be drunk. You can't drive. Keep my people still alive. And if the same don't know you. From a can of pain.


Why Stokiti Is Done With Featuring On Other People's Albums The essay hip-hop fraternity had a sad wave come through on Tuesday night when Stokiti announced that he decided to no longer offer his verses or feature on other people's songs or albums. The rapper, who is one of the ox of the game, took to Twitter to say that there was only one song that was yet to be released where he was featuring, and this song would be the last. His fans, who were clearly heartbroken, asked the rapper to share his reasons. Stokiti obliged and explained that he would still invite other artists to feature on his songs but they would know from the onset that he won't be returning the favor. Focusing Elsewhere Also it's not the end of collaborations with artists if I invite them but I am just not jumping on your project that's all. It's the difference between getting booked and doing your own productions. However, the rapper said he was proud of all features he had done since his career took flight and shared a list of some of the songs that are firm faves. Other rappers who have had the honor of having the brilliant lyricist on their songs also thanked him.