CMU Database Group · 1:23:56 · https://www.youtube.com/watch?v=aoewwZwVmv4
0:05 official members bounce bust off the Chrome realize it's real hell what we call Home official members bounce bust off the Chrome realize it's real hell where we from the ins side one I Vision fat licks and M Clips the Chrome will make the average imitator do back flips you like a [Music]
0:27 pistol just to reiterate again everyone uh that's in the class um again we have all our our friends from industry the various database companies on campus here today and tomorrow and then tomorrow morning they're having all the info sessions I posted this on Piaza it's on Piaza or it's on the website too right uh so again if you're in the class by all means come to this and if you haven't yet put your CV and your availability on the spreadsheet on pza please go ahead and do that um I think there's actually going to be a bonus info session
1:00 at 12:30 I think the confluent guys are actually decided to the comment the last minute so I I'll post on that um P where that would be I don't know what room it is so again start at 9:30 and I again I basically took everyone's preferences
1:13 asked chat gbt to write me a uh linear program to come up with the optimal schedule and this is what it produced based on availability and and preferences so it looks reasonbly correct okay any questions about this again these are like informal sessions about like they describe here's what their their system is doing uh here's some the problems they're working on here's what internships and full-time positions look like okay and we like all these people uh in some of them cases like weba sent their CTO the co-founders
1:41 here uh from Germany and then the uh The Click house guy I think he's coming in from the Netherlands as well so you know these people you can ask them technical questions they'll know the answers okay all right awesome all right so last class we were focusing on the first problem here right how are we're going to represent
2:00 data for their database on disk and so today's class now we said okay now that we know what things are going to look like in dis we need to bring it into memory to do something with it so that's what this discussion is going forward uh and this lecture would be okay how are we actually going to facilitate that that movement back and forth and how do we keep track of what do we have in memory and What needs to get written to disk uh at certain times right again the reason we have to do this is because of the voman architecture we can't operate directly on dis data data Riz on disk
2:33 there are specialized discs that can do that like some like Samsung will sell you an SSD they get arm cores on it and you can actually program do stuff down there uh but for for for General pref systems we have to assume we got to bring it into memory right so today's really about okay how do we do this and how do we make it look like we have more memory than we actually do without slowing things
2:52 down so there's two main things we're we're going to try to optimize for the first is be the spatial control which is where things are actually going to be physically located on disk and the idea here is is is pretty obvious that we want things that that are going to be used together to be stored together on disk maybe not necessarily in the same page but contiguous pages right so that way we at least try to do some sequential access to go do one one IO or one Fetch and go bring a bunch of stuff in right some systems like an spanner uh for example you can actually do denormalization meaning like I have two tables and I two have this tup has a foreign key relation the other tle I'll pack in actually the the table the tupal from one table inside the other the other tupal so that when I do ad join the data is all in one page but again most systems don't do
3:41 that the other approach is sorry the other thing we optimize for is temporal control so this would be when we have to read things into memory uh we want to try to keep that thing in memory for as long as possible uh for as many queries or operations that need it and only evict it when we don't think it's going to be used right worst case scenario is that we we we read a page do something with it for a query throw it away evict it free the memory and then next qu comes along and we just read the same page again we're going back this get again we're basically thrashing things back and forth right because we want to avoid
4:16 the the long stalls from having to read things from disc because disc can be significantly slower than than memory and so we're going to see in our buffer pull replacement policy and in our uh right back mechanisms for the background writer that that we'll try to be uh we'll try to choose things that to to to evict if we think it's be unlikely to be used which is not always easy to
4:39 do so this is a high level overview again the the diagram I showed in the beginning oh my monitor fell off well if a cops call it's here right as long as it's on that's that's all they care about all right
4:54 um yeah that one's okay okay so uh here here's our disc database a bunch of files on disk and this could be broken up into a bunch of pages right and whether it's an LSM architecture the heat file for our purposes here today we don't care and then now up above in memory we have this thing called the buffer pool and it's going to be comprised a bunch of frames and think frame is going to be the same size as as a as a database page right we just call it frames because it's the the can't use the term slot it's the location where we can put a page in in our memory and the bule manager is be responsible for managing managing uh the contents of memory and then up above in higher lay
5:33 higher abstraction level in the system we have this execution engine thing which we haven't talked about yet which will come later on and the the execution engine is going to run a query and say Hey I want to get page to and I got page got page number two from the record ID remember said that the the physical
5:51 identifier for tupal would be some record ID we could pris of a file number and maybe an object number then a page number and a slot number so given a page number we can go to the buffer pool and say hey we want to get page two well the first thing it's got to do if it hasn't done it already is bring in the page directory because that's going to tell us where to find the you know page two
6:10 then we go take uh jump to that all set in our file copy in page two and we're going to put it in some free frame in our buffer pool and again this basically be a mem copy we're going to copy the contents so what where the page is on disk and put it into memory and then now what we're going to get back to the execution engine is a pointer to page two and then page two can do whatever it wants to interpret the contents of the of that page right the bites in it by reading the header looking the catalog
6:36 if it's an LSM it knows how to you know parse whatever's inside of it you okay what do you got L for just step on it yeah there we go all right done all right is that better okay all right so right and then you can do whatever wants with page two all right so then now say the the exec finishes whatever that query is and the man decides oh I need to free up space ignoring that we have a free frame it doesn't matter we're we're going to somehow throw away what's what's in throw away the frame in uh frame the first frame throw away page two but then now if the exec Eng comes back and says hey I need page two
7:14 again the the buffer manager can say oh I don't have it in my in memory I got to go out to dis get it but it it can now decide okay I'm going to put page two into this other frame and get back a pointer to the execution engine to to where that is so the idea here is that we're giving back pointers to pages so that the rest of the system can operate on them but it the the rest of the system can't assume that the the frame is going to be sorry that that pointer
7:39 is always going to be the same location right it's always got to go through the buffo manager because that's the final operator the coordinator to decide what's in memory and where you where can you find it in memory so we can move things around as much as we want and the rest of the system will work just fine
7:55 right because I'm the high level system is operating on record ID that produces page number two that's just some something on disk and then this this thing says okay let me go get page two I know where to find it and let me go H hand you the pointer to it okay so this is the big picture of what we're trying trying to accomplish
8:14 today so I'm showing this this sort of high example with you know assuming get we're getting tuples there's going to be other parts of the databas system that's going also need memory pools and they can rely on uh this buffle manager as well but maybe not not always
8:30 um if anytime you need to be able to swap things out the dis like I'm trying to allocate a bunch of memory and I'm running out of space like as I'm running a query then you want that memory to also be backed by the buffer pool uh because it it knows how to how to move things out so we'll see this later in in the semester but there's a bunch of different things we could want to use this for like sorting and join buffers again if I'm trying to build a hash table du do my join but I want to be able to support a really big hash table that more memory than I have then I can back up bu a buffer pool and it knows how to write things out to a temp space Maybe rather than the regular database file like like a like a scratch bace or a swap space uh buffers for other doing am operations query caching and so forth
9:07 right other things going are going to need memory uh and sometimes they'll be backed by disc sometimes they're not if you want if you need to to Spill the disc and still use that memory then yes you want to back by something that looks like a buffer
9:19 B so what we're going to talk about today is sort of background of what the the buffer hole manager is going to do for us how we're actually going to implement one the policies we're going to use for it uh then we'll talk about why you don't want to use mmap in your database system uh but then we'll talk about how to do handle disio scheduling and replacement policies and then this should be optimizations we're going to finish off with a bunch of optimizations you can do uh to make your Buffalo
9:42 manager better than what the OS could ever provide for you okay and then we'll finish up with with discussion real quickly on Project one which came out last week so as I already said before the buffo manager is basically something that's responsible for organ for managing a an array of memory of fix siiz pages that it can hand out and reuse for different parts of the system that needs that needs memory right and as I said instead of what we're going to call sort of the the the the placeholder location within that array of memory that we can reuse we're going to call that a frame and that's going to be the same size as a database
10:23 page now some systems can support different database page sizes per table or per table space and they basically have to you have to have a buffer pool for each of those right you're just carving up the amount of memory that your the system is allowed to have so the idea is pretty simple that when something some part of the system wants wants to access a page that's on disk we first got to find a free frame
10:46 that's available for us and we're going to do a you know read read that file from disk or read it from whatever the remote storage and we're going to copy that into our buffer pool and we can do this for as many pages that we want and that the ordering of the data in memory
11:01 does not have to match with the ordering of the data on on disk just because it's page one page two page three in memory it won't be in that that same order because some frame was maybe free at a different time than another frame and we just put things where where we
11:16 needed important thing to understand though is that even though this is a buffer this essentially a cache uh it's going to be a right back cach meaning any rights we're going to make to these pages when we need need operate them we're going to make it to its in mem representation first and then at some later point which will Define in in a few more slides then that dirty page will then get written out and flushed out the disk it's a bit more complicated than that because there's actually
11:41 additional metadata like a log file we need to record and we need to make sure that's written a disc for the page that got Modified by that log record got written a dis but that that we'll cover later right so it's not a right through cache a write through cache would be I write into the thing on memory and then immediately gets written out the dis
11:58 right we don't want that for for protection reasons like durability reasons because we don't know whether the operation that maybe wrote that page has actually fully been saved or committed and we don't know whether we want those changes to be durable but again we'll cover that later in in the
12:12 semester so in addition to the keeping track of these frames there's also going to be this additional data structure in our buffle manager called the page table that is essentially a mapping from a page ID to some location where you can find that page in in the in the in the memory of the Buffalo manager so a mapping from a page ID to to a frame number if it
12:39 exists and so there be some additional metadata we we're going to maintain in our page table or in the buffer manager either within the page table or in separate data structures that we're going to use to keep track of what's going on with the memory that we've we've allocated and using in our frames in other parts of the system right because we don't want to
13:00 have someone say I need page two we we find a frame put page two in there and then someone else comes along says Hey I want page three and we we we take over that frame we just use for page two and put now you know put page three in there because now other parts of two parts of the system is going to have a pointer to the same frame but one guy's going to think it's page two one guys thinks it's going to be page three right so we need some way to protect ourselves protect protect our memory and make sure people aren't uh people are getting back the data that they expect so additional metata will keep track is a dirty flag
13:34 has a page been written by a by some part of the system therefore we know that we just can't drop it when we need free memory we need to write it back to the disc at some point there'll be a pin of reference counter telling us how many threads or workers whatever you want to call it how many other parts of the system are holding pointers to those pages right now and could be accessing them and then additional tracking metadata we'll see later on about the time stamps maybe when things that got accessed either from the last time or the last n number of times or k number of times and we're going to use that additional information to keep track of
14:06 what should be evicted or things like who accessed the page was it a query was it a background worker maintenance operation right was it in a transaction things like that all right so say our thread comes along and wants to access page three we look in the page table right we'll use concal mechanisms or latching to get us in there uh to protect ourselves but if we know that we once we find page three and then we're the pointer back to the whoever asked for this we'll put the pin in there increment the reference counter
14:37 to keep track of hey there's somebody out there that's that's that's looking at page three right now in this Frame so don't don't try to evict it yet let say come someone comes along and wants to access another page uh that's not there so in this case here we got to take a latch on the page or the entry in the page table cuz we want to say this thing's empty we don't want anybody else trying to insert something while we're trying to insert something into it so the latch is going to protect us then we take page two copy it into a free frame
15:06 update the metadata inside of this uh this entry to say here's now where page two is can be found here's information about who's who accessed it and what time stamp and then we can go ahead and release the latch on this entry in the page table but we're going to want to pin it obviously first because we make sure that nobody else then tries to overtake this page this this this entry in the page table and put another page in
15:27 there right so this is a high level this is what we're trying to do any questions yes page question is when will will a page be pinned it's like if I say do you have page two and I get back yes here's the pointer to it at that point pinned because I'm giving you a pointer to to page two but it's it's really a pointer to somewhere you know in my my
15:51 frames I'm holding the pointer the p is still pinned question is as long as you're holding the pointer the page is still pinned yes CU I Could Happen someone could swap out what you're pointing to because again you're pointing to to these locations in memory if someone swaps out page two with page four but you still hold the pointer to it and you want it there to be page two then you start reading things thinking it's page two and it'll read something
16:13 else yes respons this question is is the responsibility for thetion engine to come back to the buffer P manager and say I don't need this page anymore yes or whoever asked for this this page the contractor in the API is here's the pointer tell me when you're done which we can enforce because it's we're the one building the system it's not like we're trying to deal with randos on the
16:42 internet okay so back here I Ed the word latch anybody know what that is what's the latch what's that utex yes perfect so there's this distinction in in between sort of the systems or operating systems world and databases we're right they're wrong but the what they would call lock we're going to call
17:08 latch and as he said it's typically going to be a mutex right we'll cover locks later on but the reason why we can't use the word lock uh is because lock in the database world is meant to to to protect some higher level concept or logical entity within the database itself so I can take a lock on a table a lock on a tupal lock on on on an entry and an index and there'll be some extra protection mechanisms that the data system is going to provide to make sure if they're Deadlocks that you'll kill
17:38 you know you'll kill one of the the the the threads or workers holding the lock to break the deadlock right like this is locks are dealing with the outside world you know doing things on the database and therefore we have we assume they're stupid and we have to make sure that they don't uh you know they don't lock up the whole system a latch is going to be an internal protection me uh me mechanism that we as the datab system developers people building the system that we're going to use to protect critical sections because we're getting paid a lot of money to build this system
18:08 uh that we're not going to be stupid about it and therefore we're responsible for making sure that there's no Deadlocks like there isn't going to be some some thing floating above the clouds that can kill our Deadlocks it's through programmer discipline we make sure we don't do stupid
18:21 things right so in this case yes you can use a low level mutex uh you can use the the the you know the standard Library mut text which is really a few text in Linux we'll cover later most Data Systems don't want to use anything anything oper system provides you uh so we're going to roll our own mutexes ourselves roll our own latches we'll cover how to do that later um but just when we say latch get think think of like a mutex protecting critical sections and therefore we got to make sure we don't do we don't shoot ourselves in the foot have
18:52 Deadlocks all right the next question you may have is like okay what's the difference between a page table and a page directory so remember the page directory is this this thing on dis that it's going to be mapping from a the these page IDs to some page location in the database file or files right and anytime we make a change we add more pages to our table or whatever we have to update that that page table and every time sorry the page directory and and if we restart then we load the page directory back in it needs to be synchronized with the the actual files themselves the page table is an infal data structure that going to maintain in memory inside our buffer pool manager that's is going to be the mapping from the page IDs to the copy of the page existing in our buffal pool
19:35 frames so if we crash or stop the system restart the page table is going to be blown away and we got we got to rebuild it right because the second time around we might be reading it in different different
19:46 pages okay all right so now if I just said we're what we're trying to do is maintain some internal data structures that's going to allow us to map uh page you know page IDs to arbitrary locations of memory and give the illusion that we have more memory than we actually have what does that sound
20:08 like virtual memory yes so you're like okay well why are we doing all this work why even bother doing project one if the OS can kind of already do this with virtual memory right so how would you do with the O do this with the OS so OS has this this uh this feature called memory mapping or M map the basic idea is that you have some files on disk you call map open on it and that's going to literally map the the the contents of that file
20:37 into memory for your for your application and again it's going to do this lazily it's only you know it's not going to bring all the contents of the file and bring in memory but it's going to give you some starting point and an end point based on the size says okay here's the regions of memory where you can access that data and if you then try to access something that is not memory yet it'll be a page fault and it'll read it back in right so again it's going back to our database file like this
21:01 right we have this virtual memory thing here nothing's populated my thread says I want to access page one page not one is not in physical memory so there'll be a page fault while this thing goes uh the OS copies that page brings it into memory and then updates the virtual memory uh to point to now your page
21:18 right same thing if I want to access page three copy it in and we're done right what happens now if I try to access another page why I want to access page two I don't have any the US recognizes I don't have any more physical memory so now hits a page fault and says okay the thing you want is in memory so I got to decide uh which of these things I need to evict and when it does that it stalls your thread stalls your process because it's trying to be transparent to you to not know that oh I'm the thing you wanted is in memory it it's just going to stop you stop from you're running deschedule you fetch the thing you need bring it into memory and then once it's memory then you get back the the pointer to the thing you wanted
22:01 or do whatever it is that you wanted on it right so the OS is completely hiding from you the mechanism to to decide how to move things back and forth between uh disc and memory to give you again that illusion that you have more memory than maybe you actually
22:16 do all right so if I'm saying it's going to paish your thread well that sucks right if I'm running my my my query if I if I only have one thread in my system system then like I can only run you know one CR at a time it'll be a long pause while it goes and fetches things out out of out of you know out of memory in in out of you know and bring it in the disc so all right well what if I have multiple threads running at the same time won't that maybe hide some the pause because one thread could keep running while another one uh while another one gets
22:47 stalled does that solve all our problems I guess the opening slide said M's going to murder your database system so you're all you all think it's a bad idea you don't know why yet okay so here's why it
23:01 sucks the first thing is that the operating system can is AE to flush any dirty page at once at any time and I I said in the beginning that's a bad idea because if I write if I write to a a page like a an update query updates a page if I'm updating multiple pages in that single query I'm going to make sure that I make all the changes and have them all written out atomically before I say yes this this operation has completed successfully but as I said before we can't guarantee that the the harbor can write out P more than you know a 4 kiloby Page at a time so if I'm updating making a bunch of different pages dirty and I maybe still waiting to decide what's you know is this thing actually going forly complete the OS decides all right I need space let me start writing out your uh let me start flushing your dirty pages and then now if I crash and come back I got to figure out what the hell the OS actually wrote
23:56 before I crashed uh and I don't know what it wrote because it did it all for me for me underneath the covers so that's terrible we've already talked about the Stalls right since the object the doesn't know what pages are in memory because the OS is managing all that for us you can't look in the page table and say in the OS and say what's actually in memory or not that at any time you could try to touch something and then you end up stalling so how do you get around that well you could have something that like occasionally tickles pages in a separate thread so if it stalls no big deal and then that way when your quer tries go and touch it ory you touch the page doesn't up get stolen but now you're building much of extra infrastructure to overcome this this you know this this this problem with the operating system and you're building a lot of infrastructure you would need anybody to have a buffer pull manager
24:42 and furthermore how you going to know what pages to tickle tickle not bad word but you know what I mean like how do you know how do you know what pages you want to touch before you need to touch them if you haven't run the query yet so that
24:53 sucks what happens if now if there's an error right do you get an exception do you get like an error number no you get interrupt how do you handle interrupt in in your program interrupt Handler where do you put
25:11 that everywhere right because now at any time in any part of the system that you're accessing memory but it's backed by map you have to also include the interrupt Handler because all of a sudden you may try to tell something and you get a Sig bus and you got to decide what what to do with that
25:26 eror right at least if you use like the Lipsy or posic API to do F read fite you'll get back an error number it's going to lie to you sometimes we'll cover later on but at least now you like it's a single location where I know I'm going to be accessing something on dis I bring it into memory now the rest of my system can operate on those pages and memory and I don't worry about them touching something that somehow magically got swapped out or some issue happened at the OS is hiding from
25:51 me and then we're not really going to get to Performance issues but take my word on this uh it's going to be slow because what do the OS how does the OS maintain that that that mapping they basically have their own version of a page table how are they going to protect it with mutexes are they going be good mutexes no it's going to be the lipy futex one which there's better there's better ones out there even though line is statices right so now all the things we're trying to we'll see these optimization later on but all the things we can do to reduce the contention on our page table and being smart about what we're evicting and why we're evicting and when we're evicting
26:28 it all that gets thrown out the door because the OS is doing everything for us yes so for the problem is the problem that there will be too much exception or is that there's no exceptions it interrupts interruptor yes is it is a problem that there will be too much interrupt or is that the information is not enough it's question is what's the what's the problem with interrupts because the problem is that it's anytime I touch something in me in memory that's backed by the map I could get it
26:59 interrupt so it's too much it's like so you you basically need to duplicate error handling code all over the system versus like if the error is going to occur when I read something right there'll be one location in in in the disc schedule that we're going to manage ourselves to say okay now I'm doing the F read or the read go get my data and I can check at that moment of reading am I get do I get an error or not so the the
27:20 the blast radius of where that error can can break is just just located the part that does the io versus like I'm touching memory that's magally backed by map files I have to have a handling anywhere because any operation on that memory could throw an interrupt could could hit an
27:38 interrupt all right so there's some ways to avoid some of these problems but again as I'm saying it starts to smell and look like a buffalo manager you're going to build in Project one so you can use uh the M Val function you basically give OS hints about how you're going to read certain pages you're going to read these things sequentially you're going to read these things in in random uh you can call mlock on it you basically tell the OS that it can't some some memory rages can't be paged out now you can't guarantee not be written out because the OS can still flush out dirty Pages for you mlock doesn't protect you from that it just says I can't swap it
28:12 out and then you can call msync which would be equivalent to fsync would be tell it to flush out memory ranges out the dis right so there's all these tricks you can do to try to contort mmap to do what we want what we want in our buffal manager but then the day you end up building something that looks like project one and it's actually going be even crappier because you still have the core mechanism of reading things uh in and out from disk maned by the OS instead of the datab system which is always going to be in a better position
28:40 and know more about what you how the data is going to be used uh than the OS could ever be right so there's been a lot of systems that start off building map or bu basing their their their their system based on on mmap and surprising number over the years that we felt uh compelled to actually write papers about why this was a terrible idea um so there turn two two categories here there's all the systems that are make full uses of map and then the the systems that maybe started off using full map and then switched to partial uses and eventually got rid of it so I actually found out today from the web8 guy they started off using mmap
29:19 and then they realized as I was saying that it was a bad idea so they got rid of it so all these other people have have made the ous Journey of starting with map because it's quick easy and gives them some basic functionality that they would want and then turns out it's a terrible for for all the reasons I talked about before or in some cases it's also terrible if you're running in the cloud you and you want to be able
29:38 have observability in the performance usage or the the resource usage of your your data system mfes a lot of crap from you so I always like to talk about mongodb um mongodb is a very dat system despite some of the the hiccups they had over the years and one of the hicups it was that when they first came out they based entirely on map and they were they raised a lot of money they had a lot of customers they had a lot of top engineers and even after all you know all all those the engineering resources that were available to it they end up throwing away the map engine and switch over to wire tiger which is based on the buffer pool manager that that you're going to build in Project one so if mongodb couldn't figure it out then what hope does any you know random Jo Joo startup have you know without those resources seite has it but they have it for for portability reasons and it's not Turnal by
30:31 default right systems like elastic they're primarily readon uh serving read only workloads so same with Mod ADB so M might be okay in that case right you won't have maybe the safety issues that other systems have lmdb is the exact opposite of me I'm telling you never use uh mmap he's telling you use map for everything he loves it right uh and he he emails a bunch of the other uh database systems and tell them why they're doing wrong they should be using map uh so and he's the opposite of me we8 they still have some map in it uh so they're probably really down here but they'll eventually going to get rid of it
31:08 right all right so again the the thing to reemphasize over and over again the data system is always going to do a better job than any other part you know any than the operate system could ever do because it knows what the queries want to do what data has been modified what's coming up uh and can therefore can always make the best decision right the OS is not going to be our friend we need it to survive but we don't want to rely on anything that it's going to provide for us especially managing
31:35 memory and so as I said we wrote a paper on this a few years ago uh never use map in your database and we discuss all these issues and then we have there's also a short little video we that's on YouTube you can watch that basically shows the The Challenge and trials and tribulations of using map we thought this would be a way to like again evangelize our ideas and uh you know he buys an M Buffet pool manager from a shady guy in the streets and then puts in his database and then realizes it falls apart all right but anyway that that's all available
32:03 online okay so if we're going to read things into into memory uh into our buffal manager at some point we're going to run out of memory and therefore we have to make start making decisions of what what to what to evict to free up space so we can use it for for for new pages right but there's a bunch of things we need to consider in whatever algor we're going to use that decide how we want to evict things cuz we again we don't want to be
32:31 slow like the OS we want to be you know take advantage of all the things we we we can extrapolate from the workload and from the queries and the data to come come along and make a better decision so this is sometimes called the buffer replacement policies or cash replacement policies right they have a bunch of names this like one the classic problems in CS right one of the oldest problems and everyone has a paper in the space uh we have I think we have two of them I forget um so we obviously want to make sure that anything when when we decide what what pages to evict we want we want to pick the correct ones right we don't want to pick the page that's most likely to be used next by the query because then we will be thrashing back and forth the dis we need to make sure that we can quickly determine what pages to evict
33:11 quickly as possible right that means we don't want to empty complete algorithm to find the most optimal page to evict because then if our page evict algorithm takes 100 milliseconds but it only takes 10 millisecs to read the page that's not that's not a good tradeoff we need to make sure that we don't evict anything that is not durable yet meaning like we don't want things to uh you know if we haven't written out the log record that corresponds to the page or to the modification of a page we can't write that page out to the log records written out for safety
33:39 reasons um and then for the amount of metadata we need to keep track of for our for for our for our Pages we want to minimize that as possible because we don't want to use a lot of memory to keep track of all this extra metadata because we could have been using that memory for storing storing Pages
33:54 themselves so I will say this is the one of the things that's going to get differentiate the open source systems between the high-end expensive Enterprise systems like Oracle SQL Server db2 Terra dat and so forth they have spent millions and millions of dollars hundreds of hundreds of hours of of engineering to try to op optimize this thing and postgress and those other guys are just simply not going to be able to compete right the enterprise system is gonna have way more bells and whistles than what is available in the
34:23 open source ones the problem is also too sometimes they don't always talk about but they don't talk about what they're actually doing you can kind of glean it from reading the documentation but there's a lot of different options that are available in the enterprise system and we'll touch on a little bit of those as we go along so the most common buffer policy is g to be what algorithm should there like intro
34:45 CS lru at least recently used right and it's it's pretty straightforward and it works reasonably well so the idea is that for every single page we're just keep track of when was the last access right again the execution engine has to go to the buff manager and say give me page two to get back the pointer to it and at that point we can record okay what is the time stamp either the the wall clock time or a logical counter
35:10 that says here's the here's the time when this thing was accessed and then so we can use a bu different data structures to keep the the pages in sorted order like a link list or a B+ tree or try whatever and we can use that to determine very quickly when it comes time to evict something which one was the least recently used right so simple example query one comes along touches page one page one is in the middle here right and so now we're just going to move it to to to the head of the list right and then when it comes time to evict something since page two is at the tail of the list we just we just that's the one we're going to choose to
35:44 evict right so this is going to keep sort of an exact ordering again based on that the access Tim stamp there's a more simplified version of this we actually approx xim the ordering maybe not know exactly whether one thing was accessed before another one in the way L does but we reduce the amount of overhead we have to maintaining this these time stamps uh by just saying has been accessed recently
36:12 enough and the algor used to do this is called clock who here has heard of clock before small number okay this is actually what Linux uses they use they use a multi-hand clock but the idea is basically the same so this is going to be an approximation of lru where instead of according to timestamp all we're going to do is keep track of one bit per page that says has this thing been accessed since the last time I
36:35 checked and you're going to check every so often every time you got to evict something and if the bit is set to one then you know it's been it's been accessed and you can reset it to zero if the bits zero then you know the last since the last time you checked it hasn't been
36:50 accessed and so you basically map the pages in sort of circular order like a clock and everyone has their own ref bit and any time a page is access you just set the bit to one so now when it comes time to evict something I got to find a a a frame to free so I start at some location it can be random it could always be the same spot or pick up where you left off doesn't matter because eventually it all rounds out so I go to page one has this thing been accessed the last time I I checked the ref bit is sent to one so yes so therefore I shouldn't evict it but I'll set its ref bit to
37:24 zero clock sweeps around looks at this page now now breath bed is zero I know it's been hasn't been accessed since last time I checked so I can go ahead and blow it away and I I can fill it in with a new page and set its rep bit to
37:37 zero right I just keep going around and do the same thing over and again and then maybe the clock uh you know starts back over at the top this guy has been access we set it to zero yes is there reason why we load page
37:56 to so question is back here when I when I swapped out evicted page two I I brought in page five I said it's repit to zero instead of one well the idea here is that I brought it in but I I have no history about whether it's going to be accessed again so I'm going to set it to zero because maybe I I I had to bring it in I serviced the request that needed it right so that's fine I'm able to do that
38:23 because again we're still maintaining the pins on these things but I set it to zero so that way if it come back again if no if if it was a one shot one time you know read then it'll get evicted if someone else really needed it then it's bit will be set to one and therefore it won't be evicted so it all sort of just works
38:44 out right yes this question is would you delete a ramp page if they're all set to to zero so you you whatever sorry question if they're all set to one one what do you do uh well when you check and it set to one then you set it to zero you come back around and then it's it's been evicted at that point if if you're stuck in infinite Loop you basically have a counter said how many times I've looped
39:14 around and then if you just can't evict anything because they're all pinned they're all set to one then you reject the query you say I can't run or you just you send it out of memory error or something like
39:26 that but that Point like queries would run super super slow so like the human or some operator would know this thing's overloaded and do something else to tr to mitigate it all right so lru and clock are nice uh they're they're pretty simple they implement but they're going to be susceptible to a problem that with the ph and datab systems called sequential
39:52 flooding and the idea here is that if we have a query that comes along and it wants to touch do a squential scan on an entire table meaning it's going to read every single page in that table either once or multiple times case it's was doing a join then this basically going to wreck our our our buffer pole and all this metadata we're tracking for it keep track of how things are being used because now everything's going to look like it was just recently
40:18 accessed and it's going to throw away things that maybe were really hot we definitely want to keep in but because we're going going by what was most most recently accessed they'll get you know the things that are we should have kept or end up throwing away so in olap workloads or analytical quer is it's actually sometimes the most recently used page is the one you want to evict because again I'm scanning through say I'm scanning through once I bring the page in I read it then I'm never going to read that page again in that same query and maybe it's it's a one-off thing that nobody wants to read so that's actually what I want to evict
40:50 right the most recently used not the least recently used right the problem here is that is that lru and clock since they're basically storing you know a small amount of information like when was it last accessed doesn't tell you how many times it access in the past we're not in a good position to make decisions about should we actually keep this thing in memory or
41:12 not so just again show this example say I have this query here doing a primary key look up where ID equals one this is very common right in ot workloads looking up sing Single records and say that's in page zero uh we have we we have a Miss we bring it into our our buffle in this Frame
41:28 we service the query we're done but now someone comes along with Compu an average value across the entire table so that's just going to scan through every each every page one by one then at some point we're going to run run out of free frames and it's have to decide what I want to evict well based on the scan page zero was the least recently used so I'm going to go ahead and evict
41:49 this right to bring in now page three but now as I was saying before if this query shows up the same query shows up again once access that same page because that's a it's a hot record bunch of queries keep want to read over and over like it's Taylor Swift Twitter account or whatever she she's using um Instagram sorry
42:07 uh all right uh I gotta bleep that all right so what's that yes all right so anyway so so this query keeps executed over and over again page zero should be should be kept in memory but because we're only keeping track of what's least recently used it's going to get evicted and now we have you know now I have to go back to disc again and get it right so that sucks
42:29 so the way to overcome this is a simple technique called luk and it comes from a paper from the same guy that invented laog struct merg trees that we talked about a few lectures ago uh in the 1990s
42:41 and the idea here is that we just keep a little extra metadata to keep track of the last number of uh for some K references of the time stamps of when this when the page was accessed before and then when it was come time to now to decide what to evict you look at this history decide which one has the the longest
43:00 interval uh from the last time it was accessed from one one you know one one access to the next and that's the one you end up uh deciding to to evict so what you end up nicely balancing is is things that are recently accessed over and over again in in quick succession and the number of times that it has been
43:18 accessed there's some additional tricks you can do that SQL Server does uh that that P doesn't do where they actually keep track of is this page being accessed repeatedly within the same transaction like for whatever reason I I go get Andy's order record I do something then update Andy's order record well that if you're just doing regular luk that would look like those page was accessed twice but it's really in the same transaction so you can kind of technically say it's only been access
43:44 once right so SE Ser can distinguish in what context the page is being accessed and add that to its additional metadata to keep track of these uh previous entries right another problem you can to have is is with c starts right if I stop the system and come back up now I have no metadata about uh uh when things are accessed I sometimes I I sort that that out the dis um or I can maintain things like if I've recently evicted something
44:12 uh I don't want to throw away anything I'm having in that metadata about how many times it access maybe I had to temporarily write it out because I had to do some big operation I needed space but then when I bring it back in I don't want to learn from scratch all over again how often it's being accessed I'll maybe maintain a small cache and say here's this metadata you know here's the metadata when it was accessed when it was in memory before and that way I can have my my algorithm converge pretty
44:35 quickly so this is actually what post does there's a mailing list post from like 2002 again open source system so everything's public uh where someone says hey we found this paper this seems like a good idea we should do this and and they did it this is what postgress does exactly what the uh the paper
44:51 does my SEO does something a little bit different uh they have a technique they call approximate UK and the idea here is that it's still a single uh a single link list if you will of The Ordering of which pages are accessed but now they're going to actually have two entry points or two heads for the the L for the L list one for a a young section and one for an old section right and the idea here is now when a uh when someone accesses a page
45:23 it gets added to the buffer pool uh and we need we need to keep track of when was access instead of just adding it to the beginning of the l l chain we'll add it to the first time it's accessed to the the the old one so think is like hey yeah we know we needed you but I'm not going to immediately keep you along around for really long time if I put you in the beginning of the entire list I'll put you in this Middle Point here
45:47 because then if it does if it does need to be accessed then I'll eventually get upgraded here right so in this this case here page one is g to get put here we evict the last page everything slides over if I now access page one again I'm going to pull it out of this this part here and put it now the the front of the head the the young young
46:06 section right so the idea is again it's like lru 2 L K with k equals 2 where like I'll keep track of like the last time uh I was accessed am I in the old section the new section and then if I'm in the the old section then I'll get promoted to the young section so I'm even more less likely to get evicted the next time around
46:27 and eventually it gets it gets washed out because it never gets accessed again then it just moves back back down here and then it'll get evicted all right my SQL does this because it's it's easier than what postest does and SQL Ser does it's just less metadata it's like an easy extension to
46:46 L so there's a bunch of other things we can keep track of uh to decide when to evict things um we can do this on a on a per query basis or we can do it globally for the system we actually give me more fine grain in some systems we can do it on a per table basis or even per index per table space right so in the global the idea of a global uh eviction policy would be across all the queries running my system I'll decide which page is least recently accessed but in some cases what I want to do is have a small region of my buer pool be dedicated to one particular
47:21 query and then when I when I want to decide something what to evict I'm just evicting things localized for that one query that doesn't affect the rest of the system so what made this so postgress does this so when you do sequential can on postgress they'll allocate some portion of the the buffer pool as a ring buffer for that one query and then now when I if I'm doing scal scan and I'm bringing in pages one by one if I run out of space in this ring buffer region
47:48 instead of just evicting what what are the global least recently used page for my entire buffer pool manager I'll just take whatever the most least recently used p page was for that this ring buffer this portion of memory so now I'm ripping through pages and I'm throwing things out and evicting Things based on what I need and doesn't pollute the sort of the global eviction policy for the rest of the
48:11 system right and this is like per query they'll give you like 20 256 kilobytes in the buffer pool so like 32 Pages it's 8 kilobytes a page so not a lot of memory but at least it's enough to print pollution from the rest of the system so now if I do scan and postgress I evict Things based on in this sort of this sliced out region it's still accessible to the other parts of the system uh other queries because I need to know you know forgiv page no what frame is it is it located in but when it comes time to evict if nobody else actually needs it then I can go ahead and evict something that that the least recently page I
48:49 read another trick we can do is is pass along priority hints to the to the Buffalo manager about how a query is going to access a page and then now the the replacement policy can use that in decision to decide whether to evict something or not so you can almost think like a hint as like a light pin to say hey this thing is important I'm probably going to need it a lot but I'm not really accessing it right now so if you got an evict it sure you can get evicted
49:17 but try not to so this be important for things if you have indexes right which will cover you know B+ trees and tree data structure next week but say I have a query this is not real SQL but I just had this Auto incrementing Value like a serial key where the the value I'm going tot as plus one whatever the previous one is
49:37 right so how what's that going to look like in my if I insert this into a B+ tree that's sorted based on the ID well all my inserts are going to end up on this side of the tree and I keep extending the tree out in that direction so what's the very first thing I'm going to access anytime I do an insert in a tree
49:57 the route and then the path down along the what's that to to your right side of the tree so I can give a hint to the the database system says hey this these pages are kind of important so make sure you don't you know don't don't have vickies if you can't if you don't have to certainly the root page is important because that's the thing I'm going to hit over and over again now you could say oh luk would keep track of this thing being hot and being used all over again and therefore I won't evict it but
50:24 it'll uh you know just be sure you can pass along a hint right of another query like this again they're going to go down maybe any any random location but if I can give a hint to say keep the root in memory then that'll that'll make things better for
50:40 me all right so the again the buffer R policy is all about deciding which page we should evict from a frame so we can reuse it from RE use it for for another page so I've already said a couple times times that like okay well a we're giving a pointer out to the execution engine and it can do whatever it wants with it can decide it's going to update the contents of that page right insert a new entry into a new slot update something
51:06 whatever so if a page is not dirty then that's great for us when it comes time to run eviction because now I say this I don't need this page anymore I'm just GNA you have to zero it out you just copy over whatever the the the new page you want to put it copy it over the old one because they're always going to be the same size and you're not going to see any data from the his page right that's the fast path you pally just can
51:30 virtually drop a page uh from its frame and reuse it right away but it's been WR if it's dirty if it has been written then I just can't overwrite it all right I got to make sure that the the dirty page is written out the disc and it's safe on dis before I can reuse that that
51:48 frame so now in your eviction policy there's this trade-off between the the the fast path of okay I I can just drop the frame and reuse it versus I have to write this dirty page out the disc but it may be the case that the all the frames that are uh that are clean are things I definitely do not want to evict and what I really want to do is evict the a dirty page because I wrote something and I'm never going to read it again I want to write that back out
52:15 right so there's this trade off between deciding when to do the fast path just dropping something versus having to write something out because the thing I want to write out probably could be something I I could never have to come back and and be done with it
52:28 right so it's not like there's like the side buffer where we can say okay this page is dirty so let me put in this other buffer here and then that way I can use the frame and then eventually I'll write out that other other you know the dirty page because if I had that then like I just should just be using that for my buffer pool anyway like it's memory I could be using for other
52:46 things so the way we can avoid this this problem or try to mitigate this problem it doesn't you know you can't avoid it it doesn't go away um you can have what it's called a background writer where every so often the data system has some worker comes along looks in your your buffer pool looks at the frames finds whatever's dirty and then flushes and writes it out the disc the page still exists in memory because we're not evicting things there they're just kind of we're eagly writing things out the disc assuming at some point it's going to get evicted and we don't have to block why that
53:19 happens uh that's going page right out a dirty dirty page and then once it's safe then we flip the Dirty Bit the dirty flag in the page and now it's clean so now when the eviction policy runs it says oh this page is clean therefore I I can go ahead and and uh an evict it this is sort of what the OS was trying to do do for us in map right it had this background writer where it was writing out pages to kind of make sure that to
53:44 essentially do the same thing drop the ones that that aren't dirty but again because of the the OS doesn't know anything about transactions or all the other stuff are doing rest of their system it doesn't know that it shouldn't be allowed to write out a page because something El hasn't been written yet
53:58 again we'll talk about the wrad log later on but again think of that as just like the record of the information about what was changed in what location and that if we if we end have to crash and come back we could look at that log and recover any pages that have been dirtied and maybe haven't written out the disc yet the OS doesn't know any about that anything about that you can't tell it don't R flush until this thing has been flush in the in our system we can enforce
54:23 that so there's different uh different systems have different policies you can set for when the background writer uh should run they can be very aggressive and flush out dirty pages over and over again but now you're spending resources writing out dirty pages instead of using those resources to run queries on the flip side if you never had the background writer run then anytime you need to evict something now the your your the query is blocked because you have to write out flush out dirty pages so there's not any one magical answer I can give you say this is how you want to always set these things different systems do different things and expose different things to you
54:57 and this again where the secret sauce comes in for the the Enterprise guys where big can be a bit more sophisticated than the O the open source ones of when the background writer runs and what it evicts a simple trick would be I run my uh when I have to decide what to what dirty pages to write out I actually piggy back off the eviction policy the buffer P replacement policy find out what dirty pages are more likely to be evicted very soon and flush those guys out first instead of flushing out any random a
55:28 page okay all right so now I got a read and write from disk what does that look like what what what what we how are we going to do this so the the harbor and the operating system is going to have their own bunch of tricks that they're going to maintain or do employ to maximize the band they can get out of the hardware by reordering and batching IO requests
55:55 right the reason why modern like M2 drives and MV mvme drives are so fast is that you can do a lot of parallel operations on them uh and get really good throughput out of them but the so that means of course if you do stupid thing like have one thread do one read right you know at a time the system is going to be super slow even though you might be running on the most Modern Hardware so we're going to try to batch things together but the OS again doesn't know the relationship between these IO requests and doesn't know anything about whether one request is more important than another okay just sees read these files for me read these blocks for me uh and doesn't know whether one should be you know should be uh serviced before another you can set IO priority in Linux right to say like you make sure that you know these requests happen before another one but you can only do that on a per process level you can't do this on an individual request
56:47 level so for this reason most IND are going to maintain their own disk manager disc scheduler where they've given a bunch of the read write requests from the buffer pool manager and other parts of the system and they decide in what order should they actually apply them so most database systems are going to tell you to turn off any additional scheduling that OS provides for you sorry Linux provides for you and either use like the simple Dead uh deadline or the the 5o scheduler and there's like
57:12 there's manuals saying hey you're going to run my SE run you know oracle make sure you turn off all these features in the OS because it's going to cause problems for us priorities also don't work either too if you soon as you call fsync we'll cover in a second fsync basically just destroys all the priorities because because the OS says okay yes do F that's the most important thing let me flush this right away which may not be always what you
57:34 want so again the data system is going to maintain its own internal queue to keep track of the rewrite request for the entire system and then it can decide how to order them and how to service them based on the context of how they're being used right is it like a mission critical query that has a higher priority well maybe that should get serviced F first before some background worker job that's cleaning things up
57:57 right or if I'm reading uh if if if I know that something if I have two queries accessing two two different tables and this other query is holding a lot of locks on the system on a lot of tupal and therefore I want to free up those locks as soon as possible I maybe want to service that one first before this other query because if I let that if I get that first query done first it'll release those locks and then unblocks a bunch of other queries right there's a bunch of tricks like that that we can do in our scheduling policy to decide
58:26 how you know how how to how to prioritize things we're not going to talk about asyn IO in this class but there's a new uh there's a whole another way to implement disk managers using IOU ring if if you're familiar with that or asynchronous IO basically using cover teams instead of having your thread make a request and block until that this it's actually serviced you basically can say I I need this I need this block of
58:50 data you know notify me as a promise or something like that when it's actually available for me and Linux has a nice thing called IU ring that has a basically a buffer that allows you to to fill fill requests in and notify them so you could say if I'm scanning through a table uh in a query and I know I need pages one two three I could check the buffer manager I know I have pages one and three in memory but I don't have two
59:14 so I send my request for page two let that be serviced asynchronously do what are processing I want on page one and three and then when page two is available for me then then I start processing that so there's there's things like that you can do if if you control everything in in your datab system IU ring is still pretty new so not not a lot of systems take advantage of
59:35 that so again the OS doesn't know anything about what our queries want and it's always going to get in way and in some cases it's actually going to lie to us about when we start uh you know when we want you know when we start to interact with Hardware the O can tell us things that aren't actually
59:52 true so if you call F in in in in your database system against the os's file system like against the postic API well what happens that hits the file system and running inside the kernel the kernel says okay you want to read this block of data from from or page of data from disk
1:00:11 it's actually going to first check the OS page cache everyone know what that know what that is it's basically a buffer manager sitting in the in the in the OS for pages that are on disk so it's gonna have its own region of memory
1:00:26 that it's going to maintain cache pages in memory checks you know you're trying to read this file in this offset checks the page cache if it's in there then it Services your request right there otherwise then it goes down to the hardware and then fetches it puts it in the OS page cache then makes a copy for you and then gives it back into uh your your database system so essentially for every F read if you're using the OS page cast there's two copies of the page
1:00:51 there's one in user space for you the datab system and then one down in the kernel and that sucks right now we're doubling the amount of memory we're using in our system to to refile some disk and so for this reason most dat systems will use what is called direct IO or you pass the O direct flag when when you when you call F open and this is can tell the operis to bypass its page cache now any F reads any read operations go directly
1:01:16 down to through the file system down to the hardware and you get back you know the blocks of data that way and now it's only one copy uh from the kernel into you right avoids redundant copies doesn't you know the oos page cast is going to have its own eviction policies that we don't want to deal with and that way again we won't have complete control over any operations we're doing on
1:01:39 disk there's one famous datab system that does that relies on the OS page cach and it's a terrible idea anyone take a guess who it is he said what lmdb they're using M that's a whole different they have other problems
1:01:57 it's postgress postgress famously relies on the US page cach if you go read the documentation of postgress we don't have time to do a demo maybe do this next class but you can see how OS how post uses the OS page cache and it tells you when you allocate memory to postgress you they tell you only use 25% of the amount of memory that's available in the system every other datab system says use 80% of memory that's available to you
1:02:21 for the buffer pool right let let the OS have 20% or what whatever needs it to survive the D wants to take the Rest Post says only use 25 30% because they want the rest of the member to use for the page cach in the in the OS right I think this is some remnant leftover thing from from the 1980s when they first designed it the amount of memory the is the question is the amount of memory the same what do you mean amount of memory of what Prov by other this question is is the amount of memory provided by postgress the same well no you're saying like when you set a buffer manager size you're telling when the system boots up use this amount of memory use 10 gigs of memory right and that's how much they're gonna rly allocate for the buffer manager so po
1:03:06 say your box has 100 gigs of RAM right POA says Hey use use 25 gigs everybody else is going to tell you use 80 gigs because they want the extra mem to use for the OS page cache right so again that may mean something that that post guest could evict something from the buffer pool and it still exists in in the Usos page
1:03:27 cash they realized this is a bad idea and they're trying to get off it and there's actually a Blog article it's a LinkedIn from a few uh months ago from from somebody working at postgress at Microsoft it's hard to see the screenshot but basically there's a new
1:03:39 uh experimental feature that turns off the OS page cach and let's postgress use direct IO there's a bunch of things they want to fix for Io and postgress uh and then this is one of them that's coming out in later versions again because you don't want to let the operating system manage anything for us we do everything
1:03:58 ourselves all right let's do a quick quiz if you've taken OS class or before let's see how this goes so if our beautiful databas system calls fite what happens we have some some page that's in memory we call fite and we want to write it out to a file what
1:04:17 happens it's copied down down into uh into the kernel and the kernel then buffers it and writes it out to to the to to the device eventually right right it's going to be some some buffer layer going down all right well that sucks because if I crash now my f that I just did could I could lose data so what I need to do I got to call fsync what does fsync
1:04:44 do says immediately flush who like who's telling what to do what what's that telling the OS and Os tells who the hardware so so you the data system it's beautiful it tells the operating system hey make sure that thing I just I want you to write is actually written a dis the actual device so then the OS then makes the call to down to the to the the harbor device to say hey make sure this thing's actually getting flush
1:05:13 now the hardware can lie too because it could have batteries down there right that keep things in its own little buffer in memory so that says yeah yeah I have S no problem and then eventually it'll actually get written out so like there's a small chance of you know the the batter breaks you might lose uh your data um but the idea is that you call fsync and by the time you get response back because it's a blocking call it's a CIS call you know your thing's been written to
1:05:36 dis all right well what happens if uh if F sync fails what happens so you call F sync and you get back an error number so what does that mean did my WR succeed no you don't know if par
1:05:57 suceeded know but you don't know what sorry you don't know if it's par succeeded or completely she says you don't know what it's partially partially conceeded or partially seceded or or or or nothing been written right well Linux would Mark your dirty Pages as clean so fsync would fail and then they they would Mark the dirty Pages clean so you would get back the error number and say yeah your fsync failed but then if you call fsync again
1:06:28 be Linux has already marked the pages as clean so it would come back and say yep your fsync suceeded right so in a bunch of different database systems they would call fsync in a while loop right call fsync if it fails I just try again and because now Linux was marking these Pages as clean you come back the second time you call F sync and it says yep the OS says yep succeeded but it's lying to you
1:07:02 right so again don't do this so now you say why why why would lenux do this why would they lie to you and tell you the bir the page table is actually clean because the kernel developers worried about somebody plugging in a USB thumb drive right calling fyn on that after it's been pulled out and then uh they it never gets plugged back in So now their page table has a bunch of these dirty pages from the USB drive that's never going to show up ever again
1:07:28 and they need a way to clean up the the page table so they said oh Mark is clean that's fine right but database systems are not running off of USB thumb drives at least they shouldn't be so this is actually the worst thing for
1:07:41 us so this is actually a big Scandal that came out in 2018 it's not very long ago this is actually a bug in a bunch of DAV syst for 20 years right it's not just postgress hit this problem postgress uh MySQL mongodb and a bunch of others were basically doing the same thing actually I should have tried on chat gbt if you asked chat to write code for this probably put on a file on a wild Loop
1:08:01 right and for so what happened was some guy shows up the mailing list and says hey post lost my so much of data for me but I didn't have a kernel panic and I didn't have uh you know any air numbers
1:08:12 and eventually someone dug down into it and realized oh yeah fsync is actually lying to us for 20 years right this is why the operating system is not our friend we should never trust it and we do everything you know as much as possible try to Avid uh you know relying on it to tell us what what to be should be doing right because of problems like this
1:08:34 okay all right so we have 10 minutes left I want to blaze through a bunch of optimizations you can do in your buffal manager to make it faster some of these you could employ potentially for project uh one to to boost your ranking on the leaderboard but not necessarily and again these are the things that we can do that the oper system cannot do for us because it just doesn't know what the what our queries are wan to do what what what our database looks like right
1:08:58 again the I would say the spit is be the first one's probably the biggest win and easiest thing to do to to multiple managers the other ones are more complicated and they have various trade-offs on when it works and doesn't work um and the engineering engineer difficulties but the first one's pretty easy you probably want to be doing this I forget whether we in this in this year's iteration of project one whe it's possible to do this but all right so the first optimization is we don't necessarily to have one giant buffer pole manager for the entire entire database system itself right you can have multiple buffable instances you can have one per table one per index one per
1:09:34 table space or you know different logical databases on the same database instance and the basic idea is that we're just partitioning memory across the different buffer pool managers um and that'll R reduce the L contention we have inside the data structures because now different workers will be accessing different buffer managers updating their own lru K information and everything sort of spread out and reduces
1:09:58 contention so now you say okay how do I keep track of what page is in what what prople manager well there's two basic approaches one you can rely on the object ID that's part of the record ID that we talked about before remember when I showed in cql server we weend that function on the record ID and it split up show me there's the file number the object ID and the record the the page number and the slot number right we could use that additional metadata to tell us what buffer pool instance we should be going to right so say say like it's a high level operation like get record 123 obvious obviously this is not SQL so we take this record 123 we get back convert so convert it into what the The Logical constructs of of the record ID represent and then we take this record ID and that just we have some mapping table that tells us what bu manager we could go to and again on the Enterprise systems you can actually specify on each buffer instance like
1:10:48 what page size are they using all right what you know what lru K algorithm are they using right how the prior prioritize one page over access over another right you can spec you can set those uh protocols directly on each buffer pool and have them at man
1:11:04 separately the more easier approach is just H do simple hashing with round robin selection of the what buffable to use this is essentially what MySQL does right so for a given record ID you hash it mod n where n's the number of buffle managers you have because you have to Define it ahead of time how many how many you want and that just tells you that just tells you where to go
1:11:25 right and no matter if you whe you no matter uh you know who what what thread accesses to the same record ID it's always guaranteed to go to same same page right because a page can't exist in different multiple multiple buff pools at the same time because the coordinate across those things would be impossible or
1:11:44 difficult the next optimization we can do is prefetching or just sort of obvious thing you'd want to do if you're fetting things from dis so because SQL is declarative we know what the query wants to do therefore we can try to identify ahead of time based on the query plan what pages going it's going to access in the future and go ahead and prefetch them so for squal scan that's pretty easy
1:12:09 right I'm accting page zero I bring that in my profer pool but then now I'm I know I'm going to scan down and read page 1 2 3 4 so when I go fetch page one I'll also maybe go fetch page two and three as well and and bring those in so that now when I I come along and continue processing the page I need is just there for me right because my diagrams just look like I'm accessing page two and then immediately access you know page three and Page four there's a little bit of processing going on right that I'm not showing here up in the execution engine like I'm going to I'm going to look at the data interpret the btes run some predicate on it maybe update some additional metad data or build a hash table so it's not like immediately after I access page one I access page two and so forth I have maybe a couple micros seconds uh to go fetch the next thing
1:12:52 and bring those in so soal prefetching that's that's not that fancy actually OS can do that in map like they can prefetch in sequential order both in forward Direction and reverse Direction but what they can't do is index pre-etching because again it doesn't know what these Pages represent doesn't know how they're connected to each other it just sees a bunch of pages on disk doesn't know that there's a higher level logical data structure built on top of them so in a datab syst you can do things like if my query wants to do a squential scan right so I start at page zero the root I jump down here to page one I bring that in memory now I jumped here to page three but again based on what the query wants to do I know I'm I'm I'm going to have to scan
1:13:37 along the leaf nodes to get more pages but now the leaf nodes aren't contiguous right it's page three page five then page six so if you were doing you know blindly sequentially uh prefetching whatever you is in order you would actually go get page two but we don't actually need page two at all we need page five
1:13:55 so in some systems like an oracle they can identify what pages I'm going to need uh based along the sibling pointers and leaf nodes and they'll go ahead and prefetch things for you right and the OS can't do
1:14:08 that yes is it true that a neighbor index pages are necessarily close your question is is it true that neighboring Pages uh so sibling Pages along the Lea nodes of the data structure they're not be contiguous in memory
1:14:25 his question is like so for are they necessarily close memory in memory no so there's there's no there's no guarantee of the ordering in memory for the buffle manager it might just happen to do it for p fetches things in an order they can't to be you know I have enough frames to go fetch them in and they're all contiguous but m not necessarily
1:14:48 right now you're getting to like cash level or cash line optimizations maybe what you're thinking about like so like disc is so much more expensive we're trying to minimize that IO not worried about like keeping things in L3
1:15:04 cach okay another trick we can do is called scan sharing sometimes called synchronized scans and the idea here is that if I have two or more queries running at the same time and they're accessing the same Pages then rather than them independently going fetching pages one by one and maybe polluting my my buffer pool I can actually piggyback the queries off off of each other so as one quer is scanning along the next query shows up and jumps on the same cursor that's iterating through the pages and just reads the same pages that the other query is
1:15:38 reading right so this this is not the same as result caching result caching is query shows up I produce some result and then the same query shows up again and then rather then rather than running the query I just reuse the cache result this is like at the lower level of the the actual implementation of the dat system I'm reusing pages that I'm accessing from for multiple
1:15:58 queries so you can do this in SQL Server db2 Terra data and postgress this is actually one of the nice features that postgress has over other open source systems Oracle support sort of supports this but the Restriction is that they can only do this if the queries are exactly the same like literally the same strings being passed in then they can recognize if these things are being running at the same you know running together at the same time they're the exact same thing I can reuse the uh the results
1:16:25 so if you look at their documentation they talk about how if you have a query select star from employees with lower case and then you with uppercase letter or an extra space here these are considered different queries because they're the strings going to Hash differently so you can't reuse them
1:16:39 whereas in in in other systems these are logically the same query and you could reuse the the scans so quickly here's what this looks like so our query starts selects uh Computing aggregation on table a query one's ripping through brings in Pages as it needs as it goes along
1:16:55 then now we get here to page three and we're going to go ahead and evict page zero because it was the least recently used and then bring in page three but now the next query shows up and wants to do basically the exact same thing right whether or not has the same wear Clause it doesn't matter and if we did the stupid thing and started from the beginning of the page and scan through like the first query did well what's going to happen well we're we're going to have to bring page zero back in even though we just evicted it so the data
1:17:20 smart and say okay well you're accessing the same Pages as uh this query that's actively running so let me just put me piggyback you go along for the ride with the first query it goes through reads the same Pages as the and process them in the same way that the first query does which we can do again under the relational model because Pages the data is unordered right so we we can exploit that here and then now when q1 finishes
1:17:47 with Q2 we kept track of okay well I I started scanning halfway through the table there's a bunch of other Pages I'm missing so let me just loop back around and and get the ones that I missed or maybe I'm lucky and there's a wear Clause that says I don't actually need to read uh other
1:18:02 pages right now what's tricky about this which we don't need to show is like depending what my query is I may actually get up slightly different results if I'm filtering things out or have have a limit clause and I don't I'm not I'm not sorting them out in any kind of order because I could run Q2 once and maybe read these these three pages and get some result then I run the second time and I read the first three pages and I actually get back to different result again on the relational model that's
1:18:29 okay right if you add like a limit 100 here all right last optimization is a technique called buffer pull bypass these are sometimes called light scans in in or originally invented in format it's called light scans and it's sort of similar to the the the buffer pull thing the the circular buffer I mentioned for postgress where I'm trying to avoid polluting the the the eviction policy tracking from other other from other Pages by localizing my my access to a small subset of pages but the idea here is
1:19:02 that instead of always bringing something into the buffer pool and updating that that all that metadata what if I just have a little memory buffer on the side just for my query and when I go read a page in I put it in that little buffer that only I can see
1:19:19 and then if I need if I if I S if I don't need it anymore then then I can just throw it away and I don't have to go update the page table or anything else in in the buffer manager right so you would do this for like you have a bunch of temp data uh like I create a temp table write something out to dis and then I got to bring it back in and maybe that I I'll bring it back in and put it into uh to my my private buffer because no one else can see it instead of me putting into uh know dis pack memory that's that's managed by the buffal manager and this one is not as common but this is one of the example of the PR systems can do that the that the open source ones
1:19:59 cannot all right so just to finish it quickly as like I'll say multiple times throughout the semester the data system is always going to be better than the operating system and memory management is certainly one of those things where we don't want to allow the AR system to do anything for us because it's always going to be uh it's just always going to make not always the wrong decision but it's going to make our lives so much harder and because we know what's going to beide the query plan we can make better decisions on evictions
1:20:24 allocations and prefetching and other optimizations all right so Wednesday next class we'll be uh we'll kick off hash tables let me quickly talk about project one all right so project one is going to be implemen your your own buff manager after all the great things I said about it uh you do the same thing so there's be three tasks uh Implement your own replacement policy based on luk a disc SC and then act bu manager instance for them and so we have basic API for all these components you're essentially filling in and connecting all the pieces
1:20:52 together so the L UK policy there'll be a class you basically need to to manage all that yourselves it's up to you to decide what data structure you want to use to keep track of these things it's okay to use things from the sdl the disc schedule be responsible for doing a background writer a reader writer for requests and this will be all based on using uh the sdl standard T Library uh promises for callbacks and it's very important that you use the latching
1:21:17 latches to make sure this thing is like you thread safe because we're going to hit it with multiple threads at the same time right basically requests come in the disc sched and you're responsible for writing things out to to dis and the buffo manager is going to sit on top of this and it's going to have a page table it's keep track of uh frames and you know run the eviction policy to decide when things get written out in and out the dis right and it's super important to make sure you get the correct order for for pinning because you know that you may end up giving up something that you shouldn't have given up and and that gets overwritten and that that'll crash your program okay so some general notes
1:21:52 uh I think I six but there's there's a subset of files in in the that we're providing you that that where you make all your changes if you change any other file to do something weird those are overwritten when you when you try to run it on grade scope um we provide Solutions only for the one task that we posted last night because that that was a late entry but everything else is going to be uh sort of private but we try to be very exhaustive in our testing so if you get through get 100% on this
1:22:19 uh you should be good to go for the rest of the semester and not have any bugs um if you have any questions please post in Patza or or come to office hours but please don't ask us like benign or simple C plus questions you got make just like in Project Zer going to make sure you write good code so make sure you use all the the formatting tools that we provide you and then uh there is a leaderboard where if you get the highest uh if your program is the fastest it's a different test it's a different Benchmark than the test you get mo more bonus points for this
1:22:48 project okay and then whoever has the most bonus points at the end of the semester you'll get some kind of bus bus tub swag I think we still have sweatshirts we have stickers or other things to give out
1:22:59 okay all right don't plagiarize we be ruined all right guys see you tomorrow and then see you on Wednesday I need something refreshing when I can finish manifesting to cold a whole B like Smith and Wesson one court and my thoughts hip hop related write a rhyme in my pants intoxicated lyrics are quicker with a simple Mo lier since I'm a city slicker play waves are picker RS I create rotate at a rate too quick to duplicate feel a breeze at a skate mik's at Fahrenheit when I hold it real tight
1:23:31 then I'm in flight then we ignite starts to boil I heat up the party for you let my girl me my mic down with oil Rec still turns with third de Burns for one man I heat up your brain give it a suntan so just cool let the temperature rise the cool it all with odds
1:23:52 [Music] he