#18 - Optimistic Concurrency Control ✸ Weaviate Database Talk (CMU Intro to Database Systems)

CMU Database Group · 1:20:53 · https://www.youtube.com/watch?v=-TA0QIwFUnU

1. <Untitled Chapter 1>

0:05 official members bounce bust off the Chrome realize it's real hell what we call Home official members bounce bust off the Chrome realize it's real hell where we from the ins side one I Vision fat licks and M Clips the Chrome will make the average imitator do back flips you like a

0:24 pistol is today we're going to continue our discussion on optimistic concurrency tool or sorry protocols um recall from last class we spent time talking about two phase locking and that was the first all right so yeah last class we talked about two phase locking all right and that was a concur protocol we would Implement in our database system that would generate conflict sterilizable schedules for us without having to know what queries the transactions were going to execute ahead of time what operations they're going to do what objects they going to touch ahead of time right and so the way to think about two Bas locking it's a what we'll call a pessimistic protocol meaning I the datab Sy system is going to assume that transactions are going to conflict so therefore it requires you to get the locks for the things you want to touch before you're allowed to touch them

1:16 right but it may be the case in some workloads and in some environments in some databases that conflicts are actually rare right and furthermore that most transactions are pretty shortlived most transactions are like jump in begin the transaction read or write a few number of things and then commit and you're done or write re write a few things and you're done like we're talking maybe the orders of milliseconds at the most of seconds yes there are transactions that can run for minutes days and hours worst case scenario weeks right but those th those are rare most transactions are in and out like think of like you loading a web page that's a transaction that's pretty fast so therefore if we assume that conflicts going to be rare and we assume that transaction shortlived then it may not be a good idea to always require them always require transaction to require locks before they start running because if I don't think they're going to conflict why acquire locks so a better protocol might be try to optimize

2:14 the system for the no conflict case where transactions aren't going to try to touch the same thing or modify the same thing and therefore uh we we can speed things up and we'll have to check at the end to whether that assumption was correct or not like when a transaction commits to see whether it actually violated serial ordering but at least now when they run they can run as uh without having to take a heavyweight lock in the lock manager like we talked about last time so the way we're going to do this is through what's called timestamp ordering conr protocols again there's basically like there not basically there are two categories of concur protocols there's the pessimistic

2:50 one that use locking and then there's these optimistic ones and the backbone for how they work is typically done through timestamps so now what's going to happen is the data system is going to assign timestamps to transactions uh and it's going to use that to determine the the the order in which they're allowed to commit and because we if we order the the the time stamps in a correct way or they assign the time the transactions allow them commit in a certain way then we can guarantee that we uh generate schedules in our system that are equivalent to a Serial schedule or conflict cizo schedule right so the way this is going to work is now time stamps are going to permeate all throughout the system meaning we're going to assign timestamps to transactions and we're also going to assign timestamps to

3:39 objects in our database meaning like for every single tup for example we'll have a time stamp that corresponds to the last time a transaction accessed or modified or did did something with it right remember I said there was that uh in the very beginning of the class of the semester we were talking about uh the layout of pages and and and tupal right we said every page had a header about keeping track of like the slot array and so forth and then every tup had a header to include things like null bit Maps or what you know what attributes are null we Al we also can store timestamps in that header to keep track of like what was the time stamp of the transaction that created this object or up last updated it right so now these time stamps are uh may not necessarily be a actual physical wall clock Tim stamp like 205 over there uh but it's going to be some integer that's gonna be a proxy for some again some some ordering of the transactions that we want to occur right typically you know best case scenario should you do 64bit

4:44 uh timestamps some systems like postc use use 32 bits right so now what we're going to say is that for a given time transaction T TI we're going to assign it a unique fixed Tim stamp that is always monotonically increasing in value meaning like we can't have time stamps go up in time and then magically jump back in time again poest has this problem because they use 32bit integers for for timestamps so they if you you run a lot of transactions you're going to have the wraparound problem and we we'll see how to handle that next class but in general like the time temps are always going forward in time the reason why you don't want to use wall clock time unless you Peg it to

5:21 UTC uh is because because of what we had this over the weekend like daylight savings now time can start moving back and forth now your transactions are moving back for in time which may you know probably would you don't want to happen right all right so there's will be some part of the system that can allocate time stamps to a transaction I'm not saying when they're getting assigned yet and also I'm not saying how many time stamps you get just assume that we can do that today's class we'll assume that there's one time stamp per trans action next class and we actually see this in postgress you may get two time

5:54 stamps so the way we implement this as I said you can use the wall clock time you can ask the your local CP you like what's what's the the current time uh again if you make it UTC you don't worry about daylight savings of course the problem is the clocks drift you know that that's hard and then depending on the granular L clock if you can only measure things in milliseconds I could have two transactions show up at the exact same millisecond and I'm not you know I would have to wait a millisecond before I can give a new time stamp

6:21 another approach is do a logical counter just again had a 64bit integer add one to it do a compar and swap real fast it's add one over and over again for every time you do trans action shows up

6:31 right that's going to be really fast we're not talking about distributed databases yet but that's going to be a problem when we go to the distributed database world because if you have a counter and another server has a counter and we're both adding one to it how do I keep those globally

6:44 unique so we got to deal with that typically the best approach is going to be a a hybrid of these two right we'll see spanner later on they actually do wall clock time and lock counters but sorry they do wall clock time but they're doing atomic clocks in every single Rack or the data center and GPS satellites or GPS receivers on the roof so they can guarantee you across you know across the world all their clocks are in sync which is amazing but most systems don't don't work like

7:13 that again the main thing here is assume that there be some integer that that that's going to correspond to the time stamp of a transaction how we get it doesn't matter but it always has to be marching forward in time and we we won't worry about wraparound So today we're going to be spending most of our time talking about about uh the optimistic en Curren protocol now this part is confusing because the category of

7:36 protocols we're talking about today are the optimistic category as opposed to two phase locking with the pessimistic category but the main protocol that everyone use uses in the optimistic con Cod protocol category is called optimistic curreny control right OCC but just just you know keep keep that in mind that there's a category of optimistic Cal Protocols of which the the optimistic protocol is the main one

8:01 then we'll deal with more anomalies that we didn't we didn't cover last time uh had called Phantoms then we'll talk about is liation levels how to actually relax the requirement for all the stuff we have to do to maintain sterilizability for transactions and then we'll finish up the flash talk from the we guys

8:18 okay all right so as was I saying the the main optimistic protocol that everyone would use is called ocu or protocol and this is a timestamp ordering based uh protocol where when transactions start the database system is going to create what we'll call a private workspace for them

8:36 and any time they read anything or write anything those those those the reads will always get copied into this private workspace and any wrs they make will also be in this private workspace that is unique to that transaction and no other transaction can look into that private workspace while they're running so it means anytime I do a write I don't acquire the lock on the global database you know the Glo Global tup I make a copy of that Tuple in my private workspace then update that and I don't need locks to do

9:06 that then now when I when transaction commits now you got to go look in your private workspace and compare the private workspace with other transactions or the global database like the global state to see whether there's there were any conflicts that occurred uh since the transaction started

9:23 running and again the ideas that these time time stamps are going to tell us the order in which the you know these transactions are allowed to make these changes and I we'll use them use those to determine whether we're violating the cizo

9:37 ordering so now if there's no conflicts then we're allowed to then apply our changes that are in the private workspace for a transaction and update the global database now everyone else can see see our changes that we've made because we've

9:50 committed so two phase locking we discussed last class that was invented in 1976 at IBM OCC here is actually invented in 1981 here CMU uh by Professor HT Kung he's no longer here uh he got stolen by Harvard uh to fix the Cs Department um back in the early 90s well I so the harvor Cs Department um was famously very uh old school like in the in the 80s like they were applying the sort of their tenure policy as they would for like other

10:23 science field at Harvard like biology and so forth and therefore the tenure case was the they they expect expect you to write a bunch of Journal papers there was this guy Phil Bernstein who who then a lot of stuff were talking about uh in in terms of transactions he was like the de's professor there he Meed all this concurrency protocol stuff but then he wrote conference papers instead of journals and they're like What's the conference paper we don't know what that is right so they denied him famously denied him tenure and their CS Department was a wreck and they they they took HT Kong from AC CMU to go fix it um and so so it's gotten better over the years but anyway all right so but but he he was actually not a database

10:57 person he was a networking person um and I I met him you many years ago and he was really nice guy all right so how do OC work so OC is going be broken up into three phases and again the the authors aren't database people so this the terminology what these phases are might be kind of confusing but we're just going to go with what the textbook says and what the the versional paper says so in the first phase they're going to call this the read phase where transactions

11:20 actually can read and write to the database right but again anytime you read and write something you're copying it from the uh the you're copying it from the the global State the global database that everyone else can read from into your private workspace and any subsequent reads that you make on objects you've already copied in the private workspace you read the private workspace copy of it so this guarantees that you have repeatable reads which is one of the anomalies we want to

11:48 avoid and then now once the transaction says I want to go ahead and commit you automatically switch into the validation phase and this is where you go sorry this is where the the data system has to go uh assign you a time stamp for your transaction so they don't get time stamps when they show up they get time stamps only when they go ahead and try to commit and then it's going to check to see whether it conflicts with other

12:10 transactions and those other transactions could either be things that that have already that have completed in the past or actually running right now and we'll see the two directions you could do so then if you pass the validation phase uh then you're allowed us go into the right phase and that's where you can then apply all the changes that you made to the to the to the global database and then there's be this right Tim stamp we're going to have for every single tupo to keep track of what was the last transaction that wrote to a tuple and we're going to go ahead and update that right time stamp in the global database to be be the transaction that we assigned to or sorry the time stamp we were assigned to in the second

12:47 phase yes when you say like private work space do you mean like a separate space on disk or is something else it says what I mean by private word space I it could at at this level we're talking about today assume that there's a memory space that we can read and write to um

13:04 that in practice would be backed by the buffer pool but doesn't have to be and the protocol doesn't care okay then if if like that bu is large that's going to take a lot of like excessive memory right the statement is if that means if the if the the workspace is large if I update everything would that take a lot of memory yes but it's worth to do it is it is it worth to do it like so

13:27 uh again it depends like if if you're it's again there's no free lunch like either I have to maintain a lock table keep track of all the locks that would require for a billion tupes or make a copy copies of them into my private workspace for a billion tupal right we'll see next class and what you're actually imp implementing in Project 4 is you don't copy the entire Tuple you copy just the diff the Delta the thing you modified so yes if I have a thousand attributes and only update one of them then I can just copy that that one attribute to my prop workspace right

14:02 postc doesn't do that postc is basically doing what we're try talking here they make a copy of the entire tual no matter if you only update one thing or all things but they don't make copies of it when you do reads in the original protocol here you're making copies in the reads if you want if you want to guarantee repeatable

14:20 reads all right so let's look what this looks like visually so now first thing to point out is that now we have our we're showing our database and we're showing as an object and a value that think object is like the the primary key or something right the unique identifier and has some value and then now we have this additional column WTS which be the right time stamp it's going be the time stamp of the transaction that last

14:41 successfully uh wrote to this to this record or this object now within our schedule Al to we have these these labels that correspond to the phases we were in will be in when we when when we run OC and again like lock and unlock from last class this is not something thec explic with call I'm just showing the boundaries here to say like what phase are we in when when we run OC for these

15:05 transactions all right so transaction T1 starts uh when we call begin we go ahead and allocate the private workspace again assuming it's some space in memory that we we have exclusive access to read and write to I would also point out too that uh although we're not talking about implementation this would have to be also work thread safe as well because you could have multiple threads execute queries on behalf of the same transaction and they may all to update

15:29 this this buffer space so just because I'm showing a one transaction don't assume that this is is is not being protected with latches as well right we have to make sure that that's thread safe as well all right so T1 starts we get a private workpace then we get the first first operations is do a read on a so again what we're going to do is copy the the object a from the global database down to our private workspace

15:51 right including again including the right time stamp which corresponds to what you know assuming there was some transaction with time stamp zero that that that inserted This Record now we have a context switch over to T2 T2 calls begin it gets allocated a private workspace then it's calls read same thing goes up to the the global database makes a copy of the record and puts it in the priv and again I'm not saying how I found a assume there's an index whatever it doesn't matter for this this level of the

16:19 protocol all right so then now it enters the it wants to go ahead and commit so say explicit calls commit and then we enter this validation phase at this point here this this is when we can assign a time stamp to the transaction uh that cor it's going to correspond to its commit order so this is important to point out here T1 started before

16:39 T2 right but T2 is committing before T1 therefore T2 is going to have the time stamp of one assuming just just counter going up right so the arrival order doesn't correspond to the commit order of the time stamps

16:53 anymore so then now we we in this case here we would look at the the read set read set of of T2 which is empty because we didn't we only read one thing and we didn't write anything and we'll talk about how we do validation in the second but but since it's read only there are no conflicts no problems so it's a lot in the right face it doesn't do anything right we just we just blow away the the the the private

17:17 workspace but then now we switch back over here to uh to T1 T1 does does the right on a so again that will be modifying the the the entry in the Pate workspace but now we set the the right Tim stamp to Infinity because at this point T1 doesn't have a time stamp because it hasn't started the begin the commit process so we just set the the right time stamp to infinity and that's enough to keep track of that that you know that's the value that we

17:45 wrote then now when it does the read on a it doesn't go to the global workspace or the global database it just reads the same entry that it that it modified down here and this guarantees now you have repeatable reads I read the same thing that that I wrote or read the same thing that I read

18:01 earlier now when it goes ahead and enters the validation phase now the DAT system allocates is at a time stamp so this one time this this transaction will get time stamped too we do the validation to check to see whether we conflicted any other transactions uh and again T T2 is gone

18:17 right so there's no conflicts here so we'll go now get allowed to enter the right phase at which point we'll let uh overwrite the infinity time stamp with the time stamp we were allocated and then we go ahead and install the change up

18:33 above so again think about the in the order in which things got committed right so even though again T2 arrived before T1 T1 read a uh that was allowed to happen right and this guy writes a that was also allowed to happen too because if you think of like in the order in which the transactions are actually being committed even though T2 started before T T2 started after T1 the end state of the database as is is as if

19:06 T2 started before T1 right we could do the same thing in two phase locking as well right so if if T1 took took a shared lock on a T2 got the shared lock on a those are compatible they can both get that T2 goes ahead and commits then T1 escalates or upgrades the the lock lock to a right lock exclusive lock that you know this would have worked just fine

19:38 too all right so again the read phase is pretty straightforward like I said all we have to do is just track all the the the read WR sets for every transaction and store those changes in the private workspace if you want to guarantee repeatable reads you have to make a copy of anything you read and put in in the private workspace if you don't care about repeatable reads then then you don't have to do that

19:59 right we're going to ignore now for what happens with we update uh if we update records that have tupal because now or sorry has indexes so now the question would be okay how do I find my index is pointing to the global the global database how do I also know to also look in my private workspace um you know would you basically just do an extra check to see I know I know where the record ID of the thing I should be looking at through the index do I have

20:26 that my read write set my work space yes can we go back to the yes so let's say T2 was reading a and then writing a let's say a was a number integer equal to one yes uh so T1 would read it so a isal to one for T1 then T2 would read

20:51 one write let's say it's incrementing it so to write then T1 still think a isal to one and also increment two so so your question is what if T2 did a read on a followed by a write on a yeah and let's say every right increment doesn't matter it's again we just see reason right we don't care what you're actually doing right so what what would happen here yeah so we'll get that in a second the be the EV validation phase

21:23 when this guys goes goes a validate we'll see this liter next slide there's two you could look at to see whether I have conflicts you could look at forward in time or back in time okay so this behavior is only because we don't

21:38 write that that they're allowed to commit I me this for this simple example uh it doesn't matter what the validation step doesn't matter where you're going back in time or forward in time right if if you add a right over here then when this gu goes to validate it no either this guy could abort or this guy could abort depending how we're doing validation next slide okay okay yes so what do you mean by repeatable

22:02 repeatable re just means that like if I read he reads A up here this guy reads A and sees the value going back sees 1 two three if I immediately read it again do I get 1 two three

22:16 is are there system that doesn't guarantee this this question is are there systems that that don't guarantee repeatable reads yes well end of this lecture you'll see what why he says postest uh postgress will give you uh gives you recommitted there's isolation levels that tell you how what anomalies you could incur but again they could occur doesn't mean there will all right so let me let me follow up with what he was asking like okay you throw some rights in here what happens well again this is

22:50 this is going to depend on what the validation phase is so again when we hit the validation phase basically when they call commit the data system is can then figure out okay are you allowed to commit and in what order should I expect to to commit you so the visual algorithm and what we'll talk about here today is keep it simple we do serial validation meaning only one transaction can check to see whether it's allowed to commit through the validation phase uh if you want to allow parallel validation it's a little more extra work because now you got to you have to uh have transactions look in the rewrite set of other transactions at the same time and you have to like

23:25 maintain latches it may sometimes you want to order things a certain way void Deadlocks like we let's keep it simple just keep it seral threaded so again the goal of the validation phase is to figure out whether their transactions allowed to commit and so that we can guarantee that we only allow for serializable schedules

23:40 and the two approaches are going to be in what order do I look for conflicts do I look back in time to see whether transactions that I've already committed and I missed and my transaction missed their updates or am I look forward in time meaning I'm making changes that I know other transactions in the future

23:59 again think logical time in the future that they they should have saw saw but did not so again keep it realis for validation is checking whether committing transaction intersects its read write set with any active transactions that are still running but not have committed and again we meaning they haven't entered that validation phase and then backward validation is going back to see are there transactions that made changes that I should have seen but I didn't and therefore if I am allowed to commit then I would have violated that serializable order because then now either my entire transaction or part of my transaction is magically going back in time to a state of the database that existed uh before I was you know existed uh when I started running that I shouldn't be able to see because these other guys have already committed and they've already told the outside world they've installed that

24:49 state so we're going to do just forward validation but it's it's uh I think one of the homework assments is ask you going backwards but the logic basically works the same way it's just in what direction you're looking

25:02 at so with for validation we're going to sign a time stamp to every transaction when they enter validation phase and then if our uh if our transaction is is going to commit then there's one of the following three conditions have to hold for every other transaction that is running at the same time so basically when I when your transaction commits under Ford validation you know what the system knows what other transactions are active and you go look in their rewrite sets their private workspaces and see what work they've done and then for each transaction as long as one of these three cases is true then you you're not conflicting with with that particular transaction and if you don't you don't conflict with all possible active

25:46 transactions then you're allowed to commit all right so the first case here is pretty obvious if my transaction say I'm T1 I want to go ahead and commit if T1 completes Its Right phase uh before I even start completing my read phase sorry T say T2 wants to commit here T1 is already

26:07 committed uh sorry sorry T1 wants to commit T2 is is going to start running in the future but in this case here if T1 has completed the the the right phase before T2 has even started then that's the that's the same thing as serial order right again if my transaction is going to commit today and your transaction is going to start tomorrow

26:28 like I don't know about you can't know about you so therefore we can never conflict right now this this is this means because there may be some transactions uh like if I move this begin to the top say two transactions show up at the same time but one of them hasn't even started running at all they haven't done anything they haven't read anything haven't written anything I can't conflict with them so it's it's uh it's trible to

26:54 do the next case would be if T1 my first transaction completes Its Right phase before T2 starts its right phase meaning it's still running it's still could be doing reads and writes on the on the database um and T1 is not modified any object that's read by T2 then I know there isn't a conflict and it's safe for T1 to

27:18 commit more simp uh simply to think about is I had the right set of my first transaction T1 if the intersection of my right set with the reset of of another transaction is the null set then you didn't read anything that I you didn't read anything that I wrote so therefore we can't

27:36 conflict if our resets intersect who cares that's fine right there's a commutative but if I write to something that you should have uh that you read which should not have happened because I haven't um if I sorry if I write to something that you've you've read but you've physically read it in the past but logically you should have read it in the future then then we're violating that that time stamp

28:02 ordering so again let's look example here so T1 starts you get begin right so we create create the workspace then the first thing it does is does the read on a so again we just copied that into our private workspace no big deal we saw that before uh now I do the write on a and again I install that update to a in in my private workspace and I set the time the right time stamp to

28:24 Infinity now there's a context switch te 2 starts running a calls begin the system allocates its private workspace and then the first operation is to do a read on a again so it's getting the copy from the global database that was created at time stamp zero right it doesn't know anything about this other transaction running here so you can't see that right

28:46 yet now I enter the the validate phase for T1 and at this point here because the right set of T1 intersects with the res set of T2 then we can't allow T1 to commit because again think about what would happen if I allow T1 to commit here it's going to get time stamp one

29:06 right so the the state of the database is now at time stamp one but when T2 goes to commit it's going to get time stamp two meaning it should have saw the state of the database at uh at time stamp two but it really saw it at time stamp

29:23 zero right so it read something back in time that it shouldn't have seen so therefore this is a conflict we can't allow this we can't we can't allow T1 to commit so in forward validation we're killing ourselves because we we well actually in either one you're always killing yourself the the determination is whether uh are are people going to miss changes that my transaction made or did I miss changes from other people's transactions so so forward validations

29:50 is making sure that other people don't miss your changes if I just change it up like this so T1 now does the begins does the read on a that's fine does the WR on a sorry does the read on a and then there's a context which T2 starts T1 does that right uh T2 does the

30:13 read now T2 enters its validation phase before T1 does so under the first case t2s uh right set cannot have any intersections with the the read set of of of T1 in this case here this it didn't write anything it only read a

30:32 right so it read the version of a that existed logically at time stamp zero so that's fine we we it's committing before T1 finishes so it's allowed to go ahead and complete its validation now there's a conct switch back over to T1 now T1 goes to its validation phase right and we know it's safe to commit because T2 has completed its validation it got time stamp one I'm going to commit now T2 one T1 is going to commit it's going to get time stamp

31:05 two both T1 and T2 read the the version of a at timestamp zero which was the latest version for the most recent version for both of them most recent time stamp so logically the read of done by T2 on object a occurred logically before the read on a by by T1 and then the right on a by T1 happened after that in time even though physically it occurred before

31:40 it is this clear again there's like these two Notions of time going on there's like the time in which pH things physically happen and a time in which the data is enforcing that they happen logically is this clear

31:54 yes uh during that validation we obtain the lunches from other transactions otherwise they can might concurrently other things as well his question is in the validation phase how am I protecting the trans transactions from from each other right so I'm saying keep to keep it simple assume there's a a global latch in or in the entire system that says the validation latch and only one transaction is allowed to have that at a time so only one transaction can validate

32:28 in practice you obviously that would be a bottleneck right so yes you you you protect these data structures uh with latches to make sure that you're reading them they're writing to them at the same time there's other tricks you can do like if you make sure that you only if you examine the objects in lexor graphical order meaning like ABC in that order and then everyone follows the same order then you don't worry about like Deadlocks like I'm trying to acire a latch on thing you have you're trying to a latch on thing I have everyone goes and locks up in the same order it's sort of like when we saw two phase locking go to the hierarchy or the B plus3 like everyone's going in the same direction

33:03 that that avoids that problem but yes you would have to you would have to protect each other during this period all right so the last case is basically the the extended version of case one or sorry Case two where my transaction is committing T T1 is committing and I need to make sure that my my right set doesn't intersect with the read set of the other transaction and then my my reset also doesn't intersect sorry my right set doesn't intersect with their right set so going back here now um if now I do uh in this say prior to this I've already set up the database so T1 red a and wrote to a

33:41 T2 red B and wrote R sorry red B and red a uh but now if I'm not validate step here it hasn't read a yet and I don't know whether it's going to read a because again I don't know that the quer is ahead of time so this this case here there's no intersection between the the the the right set of a sorry right set of T1 with the the Rita WR set of T2 so therefore it's safe to go ahead and commit

34:11 this right we go ahead and give it give it a Time s so we update the private workspace and set the time s to one and then that gets applied up up here and then later on now when T2 reads

34:25 a right they will then see the the new version that T1 installed and again that's okay because now again the time stamps are moving in the correct order uh over time so so when it goes inv validates it'll get time stamp T2 sorry time stamp

34:45 two so the way they going to think about about forward validation is that say this transaction in the middle here is is going to commit so in in in the sort of the the physical time in which the transaction is committed

34:59 the scope and what we need to examine is since the beginning of our transaction and then we have to look at the readwrite set of all other transactions that are still running at the moment that we're committing or that the moment that we're in the we're in the validation

35:14 step so you don't care about what transactions ran in the past because they've already committed who cares right that that was case one we talked about backward validation is the opposite backward validation says that assuming T2 is one1 commit here that I don't care about any active transactions that are still running I only care about going back in time for recently committed transactions and checking to see whether they wrote something that I should have seen but I didn't because the change that they made was in a private workspace like if T1

35:47 made a change uh made a change like to an object say T2 reads A here T1 writes the a here it's in his private workspace and then when it gets commit committed then it gets applied to the global database and therefore T2 missed it so I got to check to see did someone write to something I should have seen if I was running in seral order but I didn't yes how do we determine which transaction to

36:13 cut this question is how do you determine which transaction to look at to go backwards so you you would have to you Bas you basically you know what objects you you you read and wrote so you go look to see in the data base is the right Tim stamp uh greater than what the right the time stamp that I saw when I brought it back in when I brought into my private

36:39 workspace right and again in in uh in the backward Val validation I don't need to look forward in time because if this transaction now commits it's going to do the same thing it's going to look back in time to see what it

36:52 missed right so you don't need to go in both directions you you just have everyone going in the same direction and that guarantees you won't miss anything yes valid and writing does that to this one here yeah if the validation for T1 that succeeds because T2 hasn't read a yet yes but if the right happened later on

37:18 after like this thing yeah so do valid right to that yeah like yes yes but like the algorithm specifies separate phases but like you'd have to without bringing in locks you could like you you could have like a a way to post and say hey guess what I I'm validated I'm about to update these things make sure you you get the latest version that I'm about to put in right okay that's one way to do it or you just go just put them right in yes forward and backwards is there like one that's better or this question is between forwards and backwards it's one better than other

37:57 they're basically the same is one that's the other question is one one more commonly used than the other uh actually that one I don't know the answer to um yeah most systems are going to do 2pl or TP with multiv vering next class we'll talk about multiv vering basically it's going to be almost the exact same thing here except now there it's in a private workspace the versions end up in the global workspace but then you use time STS to figure out what versions you be seeing but you can you still use it's complicated you can still use locks or you can use two phase locking or OC with multiv versioning and so

38:35 the uh there's other consideration there I I put this way there's other things you you have to worry about of how you're going to do multiv versioning that are going to matter more whether then you're going backwards or forwards and that'll be next

38:51 class yes so is it possible to record the time stamp at the beginning of the transaction instead of his question is is it possible to assign the time stamp at the beginning of the transaction rather than at the validation the problem with that one is you

39:08 you if you did that then you need to make sure that no one violates that now I would say it would open up less opportunities for you get less parallelism that way because you're basically then defining a Serial

39:26 order cuz it go look so so if I sign a time stamp when I start uh need go back here to this one here right because this one got the lower time stamp than the other one so this guy starts I give him T1 uh sorry T1 gets time stamp one T2 gets time stamp two then I need I need to make sure that um when I go to commit like I did I did I see what I should have seen at time stamp two

39:59 right but then how in case of OC I don't know about this this right over here because that's in the private workspace and depending when I'm doing backwards for validation if you're doing forward validation you could see that and in that case you would then have to abort because I should have read I should have read the database at at time stamp one

40:19 because that's that's this guy made that change but I didn't I read it at time stamp zero that would not be conflict realizable and I have to abort okay um so let the cover so let me jump through this this is asking you what he was asking for how to do uh seral versus parallel commits so in practice OCC works well when the number of conflicts is low like if your database is huge and your access pattern for your transactions is uniform meaning I have a billion tupal and a given time a transaction two transactions are not touching the same tupal

40:57 then this is going to be fantastic it's be really fast if all your transactions are read only even faster because you're not taking shared locks right and then you can do what we'll see next next class on multiv verging you actually don't even make a private

41:08 workspace right if everything's read only um but of course it's going to have like not all you know not all workflows are going to look like that and so we made a big deal about how going getting the locks and the lock tables was very expensive and two days locking well overhead the overhead of copying that Tu to your private work phase is expensive

41:29 again we can mitigate that by taking Deltas but still it's you're it's copying memory and that sucks there's the right phase the validation right phase are going to be bottleneck as we said before because now I got to take latches to protect data structures as implying those

41:42 changes furthermore the the the cost of an aborting a transaction is way more expensive in two in in OCC than 2pl because in 2pl if I can't if I have to touch a billion things and I can't get locked for the first one uh then and I abort then I really didn't waste anything but in OCC I would do all you know update all the 1 billion things

42:04 then go ahead and commit only to find out that the first thing I tried to modify I wouldn't have gotten the lock for it anyway and therefore I had to roll back everything you have to run transaction to its

42:14 entirety just to find out whether you know it's is actually going to be successful or not in the extreme cases if you have like everybody's updating the exact same tupal right then there's no difference between TPL and OC just it just generates to single threat execution and no protocol is going to be better but in practice again depends depends on the uh depends on the

42:40 workload okay so for OC and 2pl when we talked about it we made this big assumption that the the database was going to be fixed size meaning the transactions are only going to be able to read things that already exist or update things already exist but obviously in a real database system we have to support inserts and deletes and updates and so when we now allow the size of the data to be dynamic this is this is going to introduce additional

43:06 problems that OCC and TPL by themselves aren't going to be able to handle so let's look at an example now we're actually running SQL queries instead of just read and update operations so the first transaction wants to count the number of people in the or you know records in the people table where their status is lit right it's going to do that twice but T2 is going to start a new entry into that table so T T1 starts it runs this query

43:34 it gets count equals 99 now we have context switch to T2 it does an insert that's fine that's allowed to happen right then I come back over here and I run the same query again and now I get count

43:48 100 so it's you know it's like the unrepeatable read where I read I ran the same query I'm getting back different results which should not happen again if I was running under Sero ordering uh Ser execution I shouldn't see that because it should be I run T1 first I run the two queries get the exact same value and then T2 is allowed to do the

44:11 insert all right so what's going on here well in in two-phase locking it this wouldn't work we couldn't we couldn't prevent this because the record that caused our query to produce incorrect results the second time you run it

44:27 didn't exist the first time we ran the query so we can't lock something that doesn't exist because we don't know right we don't know what to lock it because it doesn't exist so on two days locking andc this is only going to work uh again the basic version of these protocols only work if the objects are

44:48 fixed this particular problem is called a phantom read and the idea basically is that if I scan a range of in a table a range of values multiple times in my transaction and in between one scan and another scan another transaction inserts or deletes an object then we we we end up with inconsistent

45:14 results right like it's think it's called a fan think of like a ghost or an apparition like a data is magically disappearing appearing and disappearing in a way that we shouldn't see if we were running a true serial ordering

45:29 all right so there are ways to handle this the most obvious way is just two phase locking just lock everything lock the entire table lock the entire database lock every single page on a table then no one can update anything or in sort of delete anything right of course that's going to suck that's going to be bad for parallelism so the the alternative approaches uh would be we'll go through these one by one just reexecute every scan you had when you go to commit and see whether you get the same result and that will tell you whether somebody has has slipped in uh something before you ran last time predicate locks will actually not actually look at The

46:05 Logical conflicts between different operations or different queries and decide whether there's a conflict that could produce a phantom and then inex locking will be relying on indexes themselves to actually protect ranges of things so this is going to get kind of weird now because this is now we're bringing in the physical aspects of the data structures uh to help with logical things in our

46:28 database so in practice the most common one especially in Enterprise systems is going to be index locking uh it's less common to do lock everything and again this is something you have explicitly do in in your in your application like lock the whole table because you if you want to avoid any any Phantoms um doing the executing the scam multiple times that's rare predicate locking is very very rare uh there's only three systems that do it and three of those systems are written by one guy

46:57 and he's German okay so reexecute scans this is also I say this is probably more common in uh in inmemory systems where scans are cheaper and the data isn't like you know pedabytes and pedabytes the basic idea is that you just track the wear claw of every single query that that that you run and if you notice that the

47:17 um if you notice that the sorry you check check the the the the we CLA of every single query you run and then now when the transaction goes to commit and it addition to doing the validation phase if you're doing OC or whatever two- phase locking protocol you're doing you just rerun the scan portion of those

47:35 queries to see whether there's any new new new new results right so if I have an update query has a wear Clause I make sure I update all all the all these records I don't want to run the update again when I commit I just run the wear clause and see whether I'm seeing different result

47:53 sets question yes during the re execution okay this question is when I do the reex can if I see new T I didn't see before then I abort because I know I I I'm incurring a phantom No I mean I mean when you are doing the re execution if other transaction do insertion anded

48:15 right so so if other people so we're saying the same thing if I run this the scan query again when I go to commit and other people insert things while why I'm running that scan query or before I ran that scan query I'll see different things than when I ran it the first time therefore I know a phantom occurred so therefore I conflict again you only want to do this if if you can run the scan fast if it's like in memory or small data set if I had to resan a petabyte of data you don't want to do

48:42 that you'll see sometimes the reverse of this and uh in some systems like dynb and FB can do this uh they call reconnaissance transactions basically you run the you run the you run all the queries first just to see what they read and write but don't actually make any changes then when you go to commit run it for real and see whether they actually you know that they match and then go apply the changes and roll back if you don't it's sort of it's It's the reverse of

49:10 it predicate locking is is again this this sort of this logical locking scheme where you look to see whether there's conflex over a multi-dimensional space of the locks that transactions want to hold um this is actually what system R first proposed by you know in back in IBM in the 1970s but then they deemed it like tooo impractical to actually Implement efficiently um and there's no real no attempts uh to actually do this for real except for approximations using a technique from the 1980s called Precision blocking uh and this was first adopted by the Germans and Hyper um and then ducky B copied what they did and then the guy that he sold hyper to Tableau so then he built a new system Umbra and then got forked off by cedar

49:53 cedar DB so the one dude found this paper from like 19 that had like 20 citations no one ever read that that solve this problem uh doesn't solve it entirely you know some Corner cases uh but it's good an approximation and then you know very few systems do this or it's only those four I know about all right so what are the basic ideas so again say for our scan qu we had for that transaction T1 you can think of again in the the the multi-dimensional space there's there's some bounded region that corresponds to the tupol that could exist Within this region specified by this wear clause and so it would have a logical lock on that multidimensional space and then now we all have to do is check to see if any other query is there an intersection

50:37 between its multidimensional space and and this space and therefore if they overlap this is just a two two dimensional projection but if like if they overlap or intersect then I know that the they're logically T touching the same tup and therefore that could violate the seriz

50:55 ordering again think if you have like you know I'm showing you two Dimensions here and uh two transactions but think of 100 thousands of transactions all sorts of crazy queries it becomes very expensive to do this and that's why it's not

51:09 practical right in in in general to get to do this correctly like in it uh in its full entirety it would be MP complete all right so what do people actually do instead well we're again we're going to rely on indexes assuming B plus trees uh to use them to keep track of locks on ranges of

51:30 values so that we just check to see whether there there are uh there are conflicts now between you know those ranges so we're going s of we're going to build up and go through sort of the basics of it and we'll see how we do this incorporate back into a highle locking scheme so again these locks these index locks are going to be basically the same thing as as the TU locks we sawed last class this is why I saying I was distracting away whether we're talking what the objects actually are right but you could assume they were tupal but now they could actually be

52:00 things inside of the uh inside of your B+ G so the most simple kind of lock you can have is a key value lock and this is sort of saying that within a specific value in my in in the The Logical space of of some attribute I'm acquiring a lock on that so now my lock manager I would keep track of like for this given value within this range of this of this uh B+ tree there's there's a lock for it right 14 to 14

52:29 inclusive you can have then also what called Gap locks where you can have uh keep track of the space in between the values within your index and then now you can take locks on the the empty space in between them so I can take a gap lock on 14 16 exclusive right so now if anybody tries to insert 15 right that would that would conflict with this Gap lock and I the transaction would be protected

52:58 so then now you can combine these up into key range locks where you would have for a given key you you get the lock on that key inclusive and then the Gap lock right next to it right so I could have a next key range lock to say on on 14 the and then the Gap up to it exclusive to

53:16 16 then again I'm showing this in context of a single node but obviously if you if you you want your Gap to span multiple or to the next node you could do that as well I could have a prior key lock where it's the it's the the the the value 14 and then the Gap that came before it and typically you go in One Direction because you don't want to have uh weird weird

53:39 overlaps so then now I can bring back all the high lock and we talk about last time and start taking more coar grain locks on larger portions of of ranges and then within them as sort of as I go down the hierarchy I can have more fine grain locks that are more uh That explicit locks that are more um that are locking in in in exact modes explicit modes so I could take a uh a range lock from 10 inclusive up to the gap before 16 and I'll put that in intention exclusive mode but then inside of that I'll take the uh the range lock from 14

54:15 to 16 exclusive and have that explicitly in in uh exclusive mode or I could take a another I could have another transaction come along and do a intention exclusive lock on the r that's compatible with the exclusive that's fine but then within that I have exclusive lock on a single

54:34 key right so relying on the data structure itself to help us to identify the or demarcate where we want to be able to uh maintain locks or things all right so I want to bang through uh weaker levels of isolation and there's a bunch of demos I want to show you guys help like actually running real transactions posts and my SQL and things but we'll do that do that next class um because we want to jump to the WEA talk so I made a big deal for the last three lectures about serializability how this is the gold standard in transactions this is this is the best way to write your your database system best way to write

55:10 transactions uh the dirty secret is that in practice most people aren't going to run with serializable isolation right but I wanted to teach you that first so you understand like this is what you should should be striving for uh to understand or at least have an understanding what it means to be running things in a correct order

55:26 but then now we can start turning some of these things off and and get better performance if we deem it necessary and so by default most dat systems are not going to run with serializable isolation by Turnal by default right instead there there's going to be these lower

55:41 forms and we talk about distributed databases we'll talk about weaker levels of consistency right uh how to keep you know maybe I don't need to have two nodes be exactly in sync but again we'll worry about that uh at

55:54 Thanksgiving all right so an isolation level is going to specify in in the database system what anomalies a transaction could potentially see doesn't guarantee it's going to see them because if I only one run transaction I'm not going to conflict with any other transaction because there is no other transaction but if in a highly con environment if I run at a lower isolation level I may end up seeing some of these anomalies and the reason why you want to do this is because if we if if we do less theem is doing less work to protect you from from these anomalies then there's more opportunities for parallelism and you can get better performance in exchange for potentially having wrong

56:32 results of course the question is all right how wrong can it get nobody knows dep depends on depends on so many different factors so if recall the four anomalies we talked about were dirty reads unreal reads loss updates and Phantom reads there's a fifth one called right skew we'll cover next

56:49 class so in this this sort of table here you think going from the top to the bottom the highest isolation level that in SQL you can get at least through the SQL standard is for serializable below that will be repeatable reads and this is saying that it's all the protections of serializable except Phantom reads may occur so you don't take the index locks or don't reexecute scans like we talked about below that will be recommitted where you could have Phantoms you could have run uh unrepeatable reads and you may have loss updates and again I'm underlying May because it depends on whether applications or other transactions could could cause these problems and run at the same time and the last one read committed basically says you're you're driving out the the driving out your seat belt all these things may happen

57:34 right so again simple table like this shows you that uh with seriz you're protecting from everything so how this actually implemented consuming we're talking about uh two phase locking if you want serialized isolation you execute it with strong strict 2pl with the faint and protections mechanisms that we talked about before either lock everything or reexecute scans or do index

57:57 if we want repeat reads then we just do everything as we do strong St 2pl but then we just turn off the index locks with read committed uh we run strun tobl where we hold the right locks to the very end but we we can actually release Shar locks

58:17 immediately so what does recommitted mean means again like if another transaction has successfully committed I may end up reading them their results so I may in that mind I may read a another transaction writes a and commits now I read a again and I'm going to see they're right because they they're successfully

58:33 committed and then read un committed basically says uh you know oh you can do any of these things yes what are what why strict 2pl why not strict 2 instead of strong strict I mean so though this is this is strict 2pl strict basically says uh strict is I I hold the right locks to the end but I can release share loocks uh relase share loocks as soon soon as I'm done with something but you still can't follow these 2p like I can't release locks and try to add them add them back unless you run to the lower

59:10 level so I'm going to skip this again we'll do a demo this this next class about how to actually run this and turn these things on and off um you basically say when I want my transaction run what what isolation level that I want and again that's specific to your transaction so another transaction might be running at the same time and run with serializable isolation and you may see anomalies and they

59:29 won't this is just a quick survey a bunch of a bunch of systems that are out there that and showing their first column is their default isolation levels and their maximum that they have so the main thing to point out right here for the the the the top four relational datab systems SQL Server my SQL Oracle and postr none of them the default for all of them is is never going to be serializable right typically going to be recommitted my SQL actually is

59:55 repeatable read so it has its default is a higher isolation level in case of Oracle they have this thing called snaps isolation for the maximum level this what I've saying before Oracle lies to you so if you say I want seral serializable isolation it says okay great here you go but it's actually going to give you a weaker uh isolation level that we'll see next class called synaps

1:00:16 isolation there are very few systems that run with serial by default so voltdb is the system that I help build cockro DB is uh is a open source system that distributed system and then Ingress was the precursor to postgress like before postgress it was Ingress right and by default these guys are from a seriz

1:00:36 isolation spanners here from Google and they have something called strict serializable what is that so that's the the they can guarantee that the order that transactions arrive in the system is the order that they will commit because they're doing what he was asking before how do can I assign time stamps when they show up and that's essentially what doing to guarantee that we'll cover this later db2 has something else called cursor stability which we haven't talked about what is that and we'll cover this next time but the way to think about it is in a hierarchy like this read uncommitted is at the bottom basically says you're driving up the seat belt any anomaly can occur

1:01:14 recommitted is a little bit more protection but now there's this weird two paths where we have cursor stability repeatable reads and then snap go to the other path where and this is basically saying there's some anomalies that current saite isolation that can occur in repeatable reads UNL Cur repeal reads that can't occur in saite isolation

1:01:31 cursor stability basically says like as my is my cursor is scanning a a table I'll take a lock on the page and then when I uh when I'm done reading that page I release that lock so within the page as I'm scanning it nobody else can come and modify

1:01:49 anything so now if you ask dbas or people running database systems what isolation level they're actually running so this is a survey we did a few years ago uh to just ask EBAs okay for all these different isolation levels in your data system what what isolation level you're running at and you can see that very few of them are running with serializable for most of their transactions and instead most people are running with

1:02:12 recommitted and take a guess why best performance you that best performance no default the default there you go literally what it is most people don't know what it means to have caliz transactions or if they do know they're not worth it's not worth paying the performance penalty for it so they're going to run at a lower isolation

1:02:30 level and again that might be okay all right so finish up uh as I said every single protocol that exists in the world is either going to be a pessimistic approach where you assume transactions are going to conflict and therefore you have some protection mechanism like locking to protect the objects before they're allowed to do anything to it or it's an optimistic approach where you assume that there aren't going to conflict but you still need a way to determine what in what order should they should they get uh

1:03:00 should they be allowed to commit right even if I just take them the the the order based on the r the order that I'm going to allow them to commit is the order that they arrive in the system that's essentially the same thing as as a time stamp right because just counter saying you're first you're second you're third it's the same thing there is no other way to do con protocol that I'm aware of and literature is aware of and other than these two basic approaches it's like the fundamentals of how you actually do concurrent programming uh is is based on these these two methods

1:03:26 I had one guy come up to me at a talk I get a talk somewhere he's like hey man like I have a protocol that isn't pessimistic isn't optimistic it's completely different I'm like sure go ahead and tell me right and and it was it was all right these are only two things that that you can

1:03:40 do and the it sort of related his question before like is one protocol better than another it depends on many different factors depends on many different things and it's hard it's hard to pick one there is in the academic literature some techniques to do adaptive uh protocols where like if you don't have a lot of conflicts it's OCC and then if you notice more conflicts then you dynamically switch into 2pl but as far as I know no system implements that because just implementing one of them is so hard so in a real system like a post or my SQL to have both of them

1:04:09 and make sure that both correct is is a big challenge all right so next class we're going talk multiversion Curr control and we can play more around with existing systems see how the isolation level affects things um but multiversion basically be the same thing we talked about so far except now in the private workspace the the the versin to keep track of or in the global workspace okay any last questions yes yeah I one question about the index locking yes how did that prevent Phantom reads do you just take a lock on the entire um index that it can't be updated before you read it again this question is how how how do these things protect from Phantoms yeah do I only take latches on the gaps or am I taking not locks not latches locks

1:04:48 right so like I could take so my example before like if I had a where status equals lit if I had an index on on the status attribute then I could take a a I could take a lock on the um I could take a gap lock from here say say say this is status equals lit into whatever the next status is and so I know that if anybody wants to come and get inserted it would have to either be like within that Gap or on on me so therefore I'm protected from

1:05:20 that all right uh so this is eain he is

2. Jump to

1:05:23 the CTO and co-founder of weate uh it's one of these new um Vector index or vector vector databases that we've been talking about earli in the semester and so he's awesome Ean go for it the floor is yours awesome thank you yay Andy Pala said I'm awesome um thank you for for having me uh I have a lot of content so I'm gonna gonna um get started right away like this is this I just copy pasted this from our sales stick this really just to to tell you like we have actual logos like people and companies that actually use WEA but I really want to get into the architecture so just skip over that before you can get into the architecture you should probably know what it is that people do with bb8 and the the most common used cases are

1:06:02 on the one hand semantic search so basically rather than searching by keyword lexical search exact matching try to search by the meaning basically create Vector embeddings with with large language models and then surge through that that meaning uh very common in e-commerce for example the the other thing that you've probably heard about is rag retrieval Lo men generation and we see this a lot in these kind of ask AI use cases so you have like separate data sets typically your own data and then you have like multiple data sets where everyone wants to chat with their own data like think of chat with your Dropbox your notion your whatever whatever kind of data you have or your email email is also super super common one um then another one is recommendations which is something that we're just launching in in beta the idea is like uh recommendations need similarity search but similarity search alone does not make for good recommendations you see these examples of like hey if you like this pepperoni

1:06:52 pizza you're also going to like this pepperoni pizza and this pepperoni pizza and they're all identical because the point of similarity search is to find the the closest match so there's more to good recommendations which is what we're trying to solve from an end perspective and then there's a new thing this is currently titled generative feedback loops is a bit of a working title and it's in in Alpha but the idea is rather than rag which you just apply on the retrieval side can you actually write that back into the database so it's kind of this this concept of the self-updating database or maybe even a self-learning database um where like you could say take everything that I have in my database translate it to Spanish and summarize it into 80 words Max and just write it back into the the database which is kind of a cool concept uh for for this next slide is architecture

1:07:36 finally but I think architecture follows business functions and those are represented in features here so he has a very opinionated list of um a couple of features that I want to highlight and this is really sort of a database Centric kind of view on the features would probably look different depending on on who we're talking to but I thought like these are the ones that you're probably most uh interested in it starts with object and Vector storage so something very very simple but the the point here is you don't have to use a secondary system just to serve the end to- end case with the for for the user

1:08:09 wva does not just return like IDs from a search and then you look up what the ID means in a secondary system but it has it all in in we which has its own uh challenges Advanced filtering support so it's not just Vector search but you can set all kind of filters that you can set in any kind of search engine or or a DB system from simple equal to not equal filter to range filter so like find all products in a specific price range for example and minority filters which may not make sense in in this context but will um later when we talk about it hybrid search the idea of like combining

1:08:42 traditional keyword-based search with Vector search U mash it together somehow for example using recal rank fusion um we8 is highly updatable which I think is in the context of databases yeah duh you want to update it it's a database um but for Vector indexes this is actually kind of kind of challenging and we have one real life use case where we're doing 150 million Vector updates per per day in a single cluster and that was kind of challenging to get there and then also kind of interesting to do that we it is distribute it so you have all the good things like replication sharding you can

1:09:15 um offload certain things to cloud storage which decouples sort of the storage and the computer bit and there is a lot of focus on performance so whether it's simd optimization whether it's algorithmic optimizations or um just good old dedicated indexes for specific types which brings me to the architecture gay um it starts with the object store which is just it's really just a custom built LSM store so lock structured mer merge tree um and we use this already said it to serve objects it has all the typical traits of an LSM tree so you write into some sort of a memory structure you also write into an append only write a headlock to to make sure your your rights are persisted

1:09:55 those are flushed into segments over time and then you have many segments which need to be compacted over time uh we have several compaction strategies for for doing that the default is just a sort of leveled compaction if you've ever played the game 2048 where you like combine tiles and they have to match the sums kind of exactly like this that's my my favorite example to to explain leveled compaction but also one one that we've seen in this this case with a lot of updates for example is um if you have a lot of data and you have a lot of updates a regular level compaction May not be enough to free the dis space if a lot of data is overwritten constantly

1:10:29 which is why we introduced an in place compaction strategy to sort of remove something that's deleted in a future segment without requiring two segments to be merged then for filters uh there's a lot of bit map indexes and it's basically an inverted index that builts on that same LSM story that we just talked about but rather than serving key value objects it serves bit maps and these are basically the the posting lists you would call them in in in sege

1:10:54 of everything that's matched by a specific filter and um even if the lists get very long like if a s single filter matches millions or hundreds of millions of objects this is still very very cheap to initialize because because it's basically a zeroc copy operation um which which yeah you just read it as fast as you can read it from disk um is sort of how F how fast you can initialize it and this is also an LSM store so basically if you have in like

1:11:21 future segments or in in in multiple consecutive segments if you have um the the same key but different IDs for this key then you have kind of a merge strategy in this example here um basically the the merch result after compaction is the content of both lists and then of course you also need to be able to delete it um so in this example sort of we we merge the list but also um remove one ID and then you end up with the the final one um next one is range indexes so in in e-commerce for example you don't just have these these exact match filters but you you could have something like give me all the items pric between $5 and $500 and a classical inverted index would really struggle with this because it could have like almost infinite number of combinations

1:12:06 depending on your float Precision um of of different values that are matched um and the way that we're we're solving this is with a bit sliced index which is kind of sort of turning this around rather than indexing the value you index the individual bits so for a 64-bit number that basically means you end up with um with 64 bit Maps which is kind of a trade-off that means for any lookup you always need to merge 64 bit Maps but it no longer depends on the number of of matches made and this is a similar concept that's also in in Apache Pino for example shout out to our friends from Star tree who who also um talked about this concept in the in the CMU database Retreat and feature base

1:12:44 also have that and both both of those uh databases have really cool block posts about it if you're if you're interested in in Reading More on this then we have the bm25 index um which we we use for hybrid search which is basically bm25 is an established algorithm for for keyword search similar similarity before there was such a thing as semantic search it was the search algorithm but for us in the context of vector search we mainly use it to like overcome limitations of of vector sech like if a model doesn't know a specific keyword or so because it hasn't been trained on it then we can Aid it with hybrid search for this we have a dis based index and there's there are a couple of sort of um well-known pruning algorithms one of them is wand which is the one that we're using right now um which allows you to not score

1:13:29 something that can't move the needle anymore in a in a way um which is good but not perfect which is why we're we're just rewriting it to use block Max wand same idea you don't want to score something um that can't move the the needle but you're skipping entire blocks and the reason that that uh we want to skip entire blocks is that because then we don't even need to read a do a block from dis we don't even need to decode it decompress it don't need to copy anything and that makes the whole thing a lot more more efficient now everything that we talked about so far was not really Vector database specific but now we come into the the vector database

1:14:05 part um we're using hnsw which you've probably heard of um it's either people consider it state-of-the-art or if not then s of variations that also um our graph-based Vector indexes are considered state-of-the-art and they're basically just similarity graphs so something that's close in the vector space is also close in that in that graph and that's the most commonly used one in in web8 and we's implementation

1:14:31 differs a tiny bit from the the um sort of paper and reference reference implementation in two areas one is the support for a large number of updates and deletes that we talked about which is mainly sort of an async process that constantly repairs the graph and it does that in a way where neither uh latency or or um or recall degrades and and this is highly paralyzable so this is in a way that that if you need more updates

1:14:59 and you need to like your repairs are not keeping up you just add more threads and that is something that that I think is pretty unique to web8 and allows us to to support cases that have so many updates and then the coolest one which we added lately and this is where I'm finally getting to minority filters is in place filtering so maybe you've heard of the uh Acorn paper the the general idea is um that you want to make filtered search more more IED with this minority uh filter problem so so basically or you want to overcome the minority filter problem and what that problem is is in that graph if you if you only allow a certain subset of points based on some hard filter

1:15:39 condition like a price condition but those are not necessarily the closest matches semantically then one of two things is going to happen either your quality drops because you ignore those points that are not in your allowed list and then your graph is not connect it well enough anymore so basically your your recall drops or you don't skip those points you still follow the points but then in a later step and this is why some people would call that post filtering in a later step step you actually prune those those points that you needed again because they're not allowed to be served because they're not matched by the filter um but you still need to to navigate through them and that just kills performance because you you need to score way too many points um even if you're not in a in a US using them and then what where the acorn paper comes in it it it's basically again the pruning strategy it sort of takes a look

1:16:32 at your neighbor's neighbors and um and evaluates those if they are on the list and it it avoids scoring them if don't have to so basically like you use them purely for navigation to get to the point and that that um improves performance quite a bit uh just released in in the most recent weeva version in 127 and then there's also this negative correlation problem which is like if you search for luxury watches and then you have all the semantic mattress close to luxury watches but then you have a filter condition like less than $10 that does make a lot of sense right because like the the semantically closest match for a luxury watch is going to be more than $10 so you find all these points that are not allowed and then basically you have this this this is what's called the negative correlation because

1:17:19 basically the the similarity search wants to go in One Direction but the filter wants to go in the opposite direction how do you marry up too and this is something where where weate has something that's also um quite unique which is using sort of enriching at search time you enrich that graph with new entry points based on the list of things that are allowed and that that sort of keeps you from from moving in the wrong direction and uh scoring the ones that that are most relevant um I know we started a bit late um are we still good for time this is my last slide um but I'm I'm also happy to skip it if we're if for out of

1:17:56 time keep going cool um okay so this is this is a road map sort of what what is next uh for for weate um all kinds of different directions um boring stuff but necessary stuff like Enterprise Readiness our back support and then we just talked about large scale uh for for hybrid search we're introducing block Max one for example then if you're if you've heard about um Vector surch in in general you may have heard about C bear or call poly um which are these these new algorithms that basically use um a lot of vectors per token and then you need multiple vectors you need some sort of a Max similarity support to to aggregate them um and again sort of efficiently prune them um on the efficiency and performance side locally adaptive quantization is one that that we're super excited about there's maybe some of you have seen my uh guest lecture at Brown earlier this year where I where I compared like different

1:18:51 quantization techniques I'm really good to get the memory footprint without degrading performance that's super cool generative feedback loops We call we talked about in the in the beginning already and then um yeah recommendations as a service as I said in the beginning the idea is that you don't just want your closest mattress of recommendations but you want like actual useful

1:19:14 recommendations um yeah that's that's it from my side feel free to connect and um please also apply to us for either our summer internship positions or our our um our um yeah full-time positions okay round Applause we're over we have time for one question if anybody has

1:19:38 one so of all the the vector databases that are out there the we8 one in my opinion has the best blog uh and the best doc documentation because they're very open about talking about what they're doing plus their open source uh I don't want to name some of them other

1:19:52 Vector databases can be a bit koi describing what they're actually doing and they say use certain words that don't match up with what other people may call stuff the VBA guys are very very open about everything they're doing and it's really cool okay I need something refreshing when I get finished manifesting to cold a whole B like Smith and Wesson one court and my thoughts hip hop related write a rhyme in My Pants intoxxicated lyrics are quicker with a simple Mo licker since on mer City Slicker play Waves of pick up RS I create rotate at a way too quick to duplicate feel a breeze as a escap mik's at fah when I hold it real tight then I'm in flight then we ignite but starts to boil I heat up the party for you let my girl R me my mic down with oil Rec still turn with thir de burn for one man I heat up your brain give it a sunt so just cool let the temperature rise to cool it off with s eyes

1:20:49 [Music]