Variable-Length Records and Slotted Page Design in Databases

[00:00:00]now let's look at variable length records these are records that have a column type that is a variable length like a string type for example and the length of the records may differ from row to row of the table because different strings will have different lengths so when we pack these things into a page it's hard to know when each where each record begins on the page and where each record ends page 2 record for for example in this picture what is the offset that record for is that another question is what happens when we add and delete records so suppose we delete a record that's small and we want to insert a record that's big it won't fit in the hole left from the record we delete it so we're going to need to think about how to manage empty space on the page so as a starting point we're going to redesign our scheme for fixed length records in a few ways first we're going to put our metadata in the end of the page the footer rather than the beginning of the page the header and we'll see why this is handy in just a minute next we're going to fill up that footer with a somewhat different kind of metadata we're gonna have what's called a slot directory so the very first entry in the slot directory all the way at the end of the page to the right so this is the first entry from the end in words is a pointer to free space and this is the place where new records are going to get inserted and then for each other entry in the slot directory we're going to have a pair which is a length of a record and a pointer or if you like an offset on the page to the beginning of the record so for example the first slot on this page is populated with a record that's length 16 and it's an offset 0 of the page so that green arrow pointing to the beginning of the page is actually stored as the number 0 that's the offset on the page where that record begins the second record is of length 24 and it's at some other offset on the page which again is an integer representing the number of bytes from the beginning of the page to where the record starts so that green arrow is essentially an integer offset on the page that pair of a length and a pointer determines the beginning the pointer and the end pointer plus length of the record right recall that the slots are stored in reverse order right-to-left so to speak in the slot directory okay so record ID 4 is this thing that's pointed to at the bottom it's the fourth slot from the right it's the one with length 12 now suppose we want it to delete that record how would we do that well deleting it's actually quite simple we're just going to set that slot directory pointer that entry there to know it's going to have a null length and a null pointer now this isn't going to affect the pointers to any of the other records it's simply an entry change in the slot directory effectively however the storage that used to be occupied by that record is now unused right it's an addressable even if we wanted to insert a new record now how would we do it well we begin by looking where the free space pointer points so we would put it at the end of the page here where the free space pointer points we'd create a new entry for it in the slot table here we'll use slot reuse slot number 4 so this is gonna be the new record for on this page and it's got a different length let's say it's 42 okay and a pointer to what is currently the beginning of free space so we copy the free space pointer in there and then we change the free space pointer to be 42 bigger than it was before to account for the space we just used up so that's how an insert would work it's really very simple it just goes at the end of the page and we update the free space pointer now inserts can go into empty any empty slot we like one of the problems that arises here is we've got free free space fragmentation on this page there's some free space up at the top from where we deleted something before and of course there's some free space still left at the end we might want to consolidate that free space to make room for a big record that gets inserted later so how are we going to do that well we're going to reorganize the data on the page we're basically going to pack all the records back together and then change the pointers to reflect the new locations of the records after we repack them okay so let's talk a bit about this reorganization let's ask some leading questions first of all is it safe to reorganize these records whenever we want and the answer is yes it is safe because people who are using the API pointing to these records our point aren't referring to them in terms of page ID slot ID so page two record for is looked up on this page by looking in slot directory number four which in turn has a pointer but everybody outside all the api's into this data structure into this page remain the same it's a page ID slot ID so that's K so then the only remaining question we have to answer is when should we bother reorganizing the page should we do it sort of eagerly or can we be lazy about it so the eager scheme would be to reorganize read when we delete a record all right the alternative would be the lazy scheme which is we don't need to reorganize until we run out of three space at the end of the page and at that point we could take the time to reorganize it's not a big trade-off but it often pays to be a little bit lazy in this case maybe the page won't get more records inserted and the time for reorganization isn't necessary a more interesting question perhaps is what if we run out of slots in the footer but there's plenty of space for new tuples well here's where having the footer at the end is a good thing so we'll track the number of slots in the slot directory we actually didn't record this before we'll need to track that so at the far right you can see we've modified our design now to have a number of slots as the first entry on the far right and we've moved the pointer to free space to the second entry so this is actually a design change from the previous picture this is the design we want in fact so we're going to need this count the number of slots as the first entry in the page okay that's fine we can still find the pointer to free space it's just one integer to the left so to speak from the end of the page all right and so we're gonna track how many slots there are in the slot directory there whether they're full or empty okay so that number is just how many slots there are period something might be empty that's fine but this is the number of slots now if we want to extend the slot directory turns out we have more tuples that we want to put on this page and there's still free space no problem we can add another slot to the slot directory going right to left we bump the count on this counter at the end and everything's good right basically the slot directory goes from the end inwards to the middle and the record storage grows from the beginning of the page inwards to the middle and when the slot directory of the records kind of meet each other that's when the pages full so to summarise the slotted page this is actually a very good general-purpose data structure for storing records on a heap file page it's good for variable or fixed length records it's a little bit too expensive for fixed length records we don't really need all these lengths right so it's a bit of a waste but it is general-purpose and it can work for both so some systems might use only slotted pages some systems might special purpose fixed length page for fixed length records that's certainly an option it's a lot of pages are nice because they're easy to rearrange if you have null fields they simply become shorter records that's fine so even with fixed length records if they're not able fields if the fields can accept the value no they're actually not fixed length records another reason why slotted pages are rather nice if you have a whole table of fixed length nominal records maybe you want to build the optimization of a fixed length format which doesn't have to store lengths but the slotted page format is general and quite useful and so it's in most systems you