#04 - Database Storage: Log-Structured Merge Trees & Tuples (CMU Intro to Database Systems)

CMU Database Group · 1:22:41 · https://www.youtube.com/watch?v=IHtVWGhG0Xg

1. Intro

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

0:27 ISS off we have a lot to cover cuz we ran out time uh last class uh so to spend a little bit going over the the the the last parts we didn't get discussed at the end of last last week on Wednesday uh and then we'll plow through the new stuff today for you guys in the class again uh should be no surprised everyone here homework one and project zero was due last night uh I think we had nearly almost perfect

0:50 project zeros so awesome congrats to everyone who finished um project one will be released it schedule will be released today it's probably going to go out tomorrow is uh cuz we want to upload the the source code and the grade scope uh and the leaderboard and the documentation all at the same time so that that should go out tomorrow and then if we have time we can discuss it on Wednesday but probably we'll have to punt till next week because it'll be based on the lecture when we start talking about memory management because you have to build your own buffer

1:17 pole beyond the class there's a bunch of

2. Database Talk Schedule

1:19 database talks coming up uh tomorrow in in Gates uh um at 6 o00 there's a tech talk from data bricks uh I think you see me talking about the most Mosaic uh llm stuff that they bought I think it was last year um so that'll be at 6 o00 I'm assuming they're feeding you at that one then there'll be a talk from Snowflake

1:40 uh at on the 12th this Thursday at 12:00 pm that will be pizza and that'll be up on the 9th floor um I have a lot of former students that went actually a lot of former students at dat brecks a lot of former students at snowflake uh and they all seem very happy and then we'll have our seminar series talking about database building blocks starting with the the data Fusion people from influx

2:00 uh on Monday the the 23rd and then as I post on Piaza

3. New Sponsors

2:05 there'll be uh on Monday Tuesday next week yes while we're having class but also uh you know outside the class time all the new companies that are sponsoring the car M Davis Group are coming on campus uh on Monday and Tuesday and if you're taking this class you're invited to both these events so the Monday will be research talks and a poster session from all the students working on various database related projects and then on Tuesday as I post on Piaza all the companies will having one hour info sessions to talk about

2:33 what they're building what what you can do if if you work there and internships and full-time positions so if you want to meet with the companies on Tuesday as I post on Patza there's a signup form uh select your availability for those for for various companies I think the only one that's not coming is confluent um and then if you just want to make money working these companies uh you should post your resume to that spreadsheet that I posted on p as well and then we'll make that available to all the companies uh you know next week okay any questions from any any of these

3:05 things and as I post in Pasa there's a bunch of companies these companies have full-time and internship offerings so by by all means please apply okay and again I've uh all those companies we like the people there we wouldn't ask anybody we who we didn't like so uh it's not like you're going to go you know you know dig ditches or do something weird that's not dat this related

3:28 Okay so last class we were presenting uh

4. Database System Architecture

3:31 again the high level overview of what a disoriented databas system architecture look like right and this is where we assume the system is designed to assume that the primary storage location of data the database itself is going to be on some nonvolatile storage device a disk right um and that the the overall architecture is going to be designed to deal with the case that like it may try to access data on behalf of a query or to do some background operation that it needs to do and the data is not in memory and it's on disk and we got to go bring it from disk into memory because we can't do in place updates on disk all right we'll cover later few few more lectures how we do that transfer uh but for now we just assume you know this there's some layout on dis and we can rewrite them so we were talking about should be tup oriented not page oriented

4:18 but the the the architecture we were talking about was a tup oriented architecture meaning that the the database the database system is is all about understanding where tupal are like what where the tupes are in Pages how they late in all the pages but everything's very tupal oriented across these Heap files which are unordered and what we sort of rushed at

5. Sloted P Page Scheme

4:39 the end is we were started talking about the the canonical implementation of how you represent tupal in in a page is through this slotted P page scheme and the idea here is that we add an indirection layer in our pages that map locations or offsets within a page to tupal right so at the within a page we have this header that tells us some metadata about what's in in this page check sums and other other related things and then there's this thing at the beginning called the slot

5:08 array uh and that's just going to be again pointing to offsets to tupal and all the tupes are going to be the bottom down here but fixed length and variable length we'll talk about in a second how we deal with uh variable length data that exceeds the size of the page if you go outside the we'll cover that but the idea is that the the the slaughter is just pointing to these offsets and it's going to grow from the beginning to the end and then the all the the tup data is going to grow from the end to the beginning and at some point you run out of space and the page is considered

5:37 full right and the reason why we want to have this slot array approach is that we want to be able to tell the rest of the system hey there's a tup in here and if you have the page number and the slot number you can get to it and no matter how I reorganize what's inside the page itself I don't have to update anything else right if I was addressing tupos with an exact offset in some location in a file anytime that that that that Tuple got moved around I got to go update whatever may be pointing to it like an index or some you know some additional data structure but having this indirection through the slot array gives us that freedom to move things around

6:18 without worrying about telling anybody else right IND direction is a very important Concept in computer science and systems it makes our lives easier you pay a cost for it of sure because now when I land this page I got to look in the slot array then find you know the offset versus just jumping to the offset but again that's a minor cost versus reading something from

6:37 dis so again now if I delete say I don't need to slotter array I could delete everything as it is but for some systems maybe I want to start the pages in memory so I could slide T four over just move you know move the btes over to reclaim that space I update my Slaughter right did now point to its new offset but again I don't tell anything outside of the page that that change was

7:05 made all right so now I've alluded to this this this addressing scheme to it'll say here's how to get to a tupal by its page number and offset or some additional metadata that isn't like a primary key which is a logical construct that the application is asking you to do in your database right some kind of physical address we're using here to identify T bolts we're going to loosely

6. Record IDs

7:29 call these record IDs right and it's going to represent the physical location of a tupal in the database you can see it sometimes from the outside world some we'll see in a second some Data Systems will actually expose this information to you but it's nothing you should actually rely on in your application because again under the relational model there is no order to data inside our tables therefore things can get moved around and this physical address this record ID may

7:58 change so it's typically going to be a composite of of a bunch of information about what the files and the pages are sometimes it'll be like the file ID and the page ID and then the slot number right and so you can look at a bunch of these different database systems they're all going to be storing slightly different things and again this is why I love about database systems is that there's a basic idea hey we need a record ID and everybody's going to do something slightly different and there's pros and cons to all of

8:24 these so you're typically not going to store This Record ID as part of the tubble because it's derived from the the tuple's location meaning I don't need it doesn't make sense to store within a tupal hey here's my page number and Slot number but I'm already in the page at that slot it be it'd be a waste of space to store this sometimes you do uh so for example in SQL light they'll store the row ID uh with it because that's the that's like the synthetic primary key they're using and they have a basically a B+ tree that says for given Ro R here's where the data is right and again most systems should never rely on this because the the IDS aren't supposed to mean anything to the outside world it's for internal bookkeeping of the database

9:04 system so let's pop open some databases and see what it looks like real quickly so first we'll do uh uh in in postgress so we have a really simple table here select star from R right simple simple table R has three tbal uh and in it so post is going to have this thing called the CT ID and so now when I write a query right I can put select star like a normally would but I can add this this this special column here CTI and that's going to correspond to the record

9:41 ID and we're going to get back a tupal or pair of two numbers incl 0 1 02 03 the first number is the page number the second number is the slot number within the slot of page architecture right so now I insert say or maybe let's delete a tu so if I delete the first Tu 101 or sorry the second Tu 101 now I do that scan again

10:10 right now you can see my the the 101 is now missing but now you can see that it didn't reorganize my page right it's still 01 for the first tupal 03 for the second tupal right and there's there's a gap in the middle because the way post is implemented they decided let's just leave the page that that empty that empty slot there and it's still correct again according to the relational model that's fine so now if I insert say a new

10:38 tupal um let's insert 103 now if I do that scan again where do you think 103 is going to end up is it going to be at the end or is it going to take over that free slot he say it's the free slot raise your hand to say free slot half all right

10:59 did it at the end and that's fine right that's okay so if I do the vacuum thing again think of that as like the garbage collector in post grass I run vacuum full that literally makes another copy of the table and just scans through your pages and writes out any visible tupal now when I scan the tupal again or scan the table again right now you see that it's reclaim that

11:26 space so that's good okay so let's pop it SE a again sealite has this uh this row ID right and it's just a monotonically increasing counter 1 2 3 four 5 six and so forth right so if I do the same thing if I delete that second Tuple

11:49 101 and now I scan again right that makes sense that it it didn't it didn't re it didn't reorganize the existing Ro for the other tupal but now if I insert now the the a new tupal right sqlite decize to keep keep counting at the

12:09 end that's fine uh there's no there's no notion of vacuum in SQL light so we can't do compaction there so now let's pop over to um SQL Server so you you can't see it here but let me I'll highlight with the mouse but there's percent signs

12:35 there right so it's percent percent physical location percent percent like it's a magic keyword in in SQL Server so now we get some kind of uh HEX number right what does that mean uh so you can ask sqlite or sorry you can ask chat

12:51 gbt with this nice little function here and now you get back what what what the that physical number means so in the case of SQL Server they're going to have the file ID the the page number and then the slot number within

13:05 that right and what file one means I don't know it's right it's some internal bookkeeping that SQL Server is doing so let's do the same thing we did before let's delete uh deleted Tuple now we run the that query

13:23 again right and this time it actually did the compaction right so I deleted this the 101 which is at slot one now when I select again now slot one is being occupied by the third tupal because se decided when I have things in memory if I delete something I have free space it's going to do compaction on that

13:47 page right and there's Pro there's there's pros and cons to doing either one so now if I if I insert sorry I insert a new tu run select on it and it put it at the end all right last last one to show is

14:08 Oracle so Oracle or like s light Oracle has this row ID thing but instead of being this monoton increasing value the way was on SQL light again it's some some bite so what we can do is again thanks to I think this one is stacking ex change there's some query here you run this right and then it breaks up that bite array now into an object object ID a file number block number page number and then a row slot and it tells you where it

14:44 is so let's try to do the same thing let's delete 101 and I run that quer again and it didn't do it didn't compact like in in post grass and if I now insert 103 right it just put it at the end again so this this record ID or row ID whatever you want to call it this is a the physical address of a tupal and all the most of the internal data structures are going to be referencing

15:20 if they want you know if they want to point at a single tupal is going to be using that that record ID and the system is going to know how to how to convert whatever that bite array that represents the record ID into a you know file number a page number and and then an offset and then offset is is in that slot

15:38 array right another example here is like in case of see Oracle the the the row slot numbers start at zero but if I went back to postgress postgress they start at one why I don't know okay all right so this two point storage

7. TwoPoint Storage

15:57 that we've been talking about the way it basically works is if I need insert a new tupal then I look at my page directory it's going to tell me what page has a free slot remember I'm maintaining that internal internal data structure that keeps track for every page how much how much space is being occupied and then I retrieve that page

16:16 uh if it's not memory from disk then I look in the slot array find a free slot then I insert my tubal assuming assuming that it fits right so that's pretty straightforward right if I need insert one thing I go find one you know I find a page with a free tupal insert it and then eventually it'll get written out the dis we'll worry about that that second part later that had run out the disc later um but that's that's pretty

16:41 straightforward but if I need to update

8. Updating Tuples

16:43 an existing tupal I need a way first thing I need to do is is get it to record ID so again we'll talk about indexes in a few weeks but assume there's some index that keeps track of The Logical uh logical Keys

16:56 like you know like a somebody's uh email address or Android ID and then the value of that key is going to be the record ID typically not always but typically and then from that record ID I can then extract out the the file number the page number whatever it is go to the page directory and say okay for this table at this file number at this page where do I find it like tell me how to get there

17:16 and then if that page is not in disk I bring that in in sorry not in memory I bring it bring it from dis into memory then I now I have the page I have the slot number that I got from the record ID I go look up in the slot array it tells me what offset I should be looking at within the page and then boom that's where I I get my

17:33 tupal all right if the new data will fit in the existing page we can just overwrite it we'll see in some cases later on in the semester and I know I keep punting down the road but there a lot a lot of moving Parts here uh if the we just if we can just overwrite the existing data and it fits we just write it other Mark the tupal that we're trying to overwrite is deleted and then we'll find a new page

17:59 as if we're inserting a new Tuple and write the updated version there yes question theze of theot to like find the best fit or like the first fit slot empty slot for insertion second why do we have to for the update um if there's already uh if the existing twole space is not fit why do we inserting a different P instead ofer the same all right so the first question is is the

18:28 fre space map keeping track of how much space is available so that when we insert a new Tu we know how big our tubal is and we want to find a page that would have that yes and if if there isn't there is free space but no one page has enough data toore my my new Tuple I create a new

18:44 page and then your second question was sorry repeat again second question was why do we decide to insert the T in the different pages the same right her question is if I need to update new update a tuple and uh if I can't fit it into the page where the current trle currently exists I have to write it to another page and for now assume I'm gonna I'm just going to overwrite it right so say my page has one kilobyte left of data uh and then but I need I need to overwrite an existing Tu with two kilobytes it won't fit in the same page so I have to treat that as a delete Follow by to

19:25 insert because I can't put it in the page where it was right cuz then if I if I can overwrite the existing tupal I don't need to update it record ID to anything that's pointing to it if I do need to uh you know create a create a new page or put it into a different page then now the record ID for that logical Tuple has changed and so I treat that as a elite file by

19:48 insert we'll talk about multiversion later that complicates things as well but like for now to assume you can overwrite things yes would it be the option to rear the to make space for the his question is if would is it possible for me to rearrange the Tuple like compact it sorry compact the the page compact the page to make free space insert yes you could is that common practice question is is that common practice uh I mean it's an it's an obvious optimization I don't know whether post does it or not other systs do it

20:17 right in case we saw SQL Server tries to reduce that fragmentation by compacting every time you update the page the idea is like I brought it in memory I hold a lot latch for it let me update as much as I can to to to optimize it and then then I release it whereas postgress is just trying to get in and out of the page quickly as possible it doesn't worry about

20:36 compaction again multiversion complicates a bunch of this and the way post does multiversion is the wrong way to do it which we'll cover later uh and so they might be keeping things around longer than they actually need to be what we'll cover that later yes and it'll come up and logging in a second too

20:55 okay so we've already alluded a bunch of

9. Updating Tuples Problems

20:58 these problems uh but this two oriented storage right the first as we said was fragmentation assuming I'm not doing this compaction um then my pages aren't going to be fully utilized but even if I am doing compaction and the slot AR Ray is going to grow this way the Tuple data is going to grow this way there's always going to be unless it's perfectly aligned there's always be a little bit space in the middle that is just unused

21:22 and they they have to sort of deal with it next problem we have is there's useless disc iio so if I need to update one tupal and I can store a thousand tupes in a single page I got to go get that one page because we said the the the the granularity of accessing discs was through database pages so I'm got I have to go bring in in case of post all 8 kilobytes even though I need to update one Tuple so I'm basically reading a bunch of data that I don't need at all to do do my operation do my

21:51 query and inserts are easy because insert you're just depending a pen toen right and you don't worry about reading things again at least during that insert operation but in the case of update I got to bring the whole thing in just update one one piece of

22:05 it and then now related to this in the worst case scenario if I'm updating a bunch of tupes say I'm updating 10 tupal and they're not all on the same page they're on 10 different pages now for a single update query I can update 10 tupal but I have to write out 10 10 different pages I got to read in 10 different pages uh again with all the wasted uh wasted data I'm fetching for things I don't care about then as I do my update now I'm updating 10 different

22:32 pages right so there's a lot of ways to IO uh architecture another wrench in this is that we're assuming that these nonvolatile uh discs the storage that we're writing our database out to the pages can support in place updates right all the ssds you have

22:53 now they don't really do inl updates it just you sort of it overwrites the whole block uh it's a little level detail we don't care about but what if you couldn't access like for this page here's the new version of that page right that once you write it page to disk you can never go back and change it you can delete it but you can't overwrite what's in it what's in it without creating a new page so this sounds kind of crazy but this is what how a lot of the uh distributive file systems and some of the object stores in the cloud it's how they work so I can only do a pens to to disk I can't do wrs or overwriting

23:28 modifying existing data so most famously this is what H how hdfs works for for Hadoop Amazon S3 sort of looks works like this uh Google has their big distributed file system Colossus these are a penon access methods meaning you can only add new things you can't overwrite existing things otherwise you just just have to delete

10. LogStructured Merge Trees

23:51 them so this is going to lead us into an alternative way to represent tuples in a database it's called a log structure storage or lock stretch of merge trees right and this is going to be try to overcome the some of the deficiencies we saw in the last slide that you would have in a tup oriented architecture where you're up trying to update slotted

24:10 pages and it's going to the way the high L way it's going to do it is that we're going to assume that we can only append to blocks and pend to pages and that'll make our rights go faster but the trade-off will be will make our reads go

24:23 slower well then look at an alternative approach which I've already sort of been alluding to as well with my SQL and SQL light where instead of having you still have slotted pages but instead of having a heap you're just going to have an index like a B plus tree or whatever data structure you want and that'll be in index organized storage and then we'll finish up talking about what tupal actually the bits of the bites of a tupal actually look like okay so again we're we're behind because we we ran over time last class but I'll try to go

24:51 uh quickly as possible but still stop me if things things are confusing all right so log structure storage the idea is that instead of having slotted Pages where we do impl updates instead the database systems just going to maintain a log think of like a ledger or a um a listing of changes that have been made to to

25:13 tupal and each log entry is going to represent either a a put operation like like installing some some some record or a delete that's like the lowest level that the the only sort of basic operations you can do on on on this uh on those log structure storage and this is an old idea that dates back to 1996 uh there was a seminal paper from I think out of UMass Boston uh for log structure merries and this actually was derived from or based on earlier work done early 90s as well on log structured file systems the idea that you're just storing log records uh about what changes have been made and then when you want to read them you sort of replay the

25:55 log so in a log seure storage system a databas system there's going to be two data structures there's going to be an inmemory data structure called the mem table that we're going to use to actually do in place updates for uh for for the database for tables but it's not going to be the data structure is not going to Encompass or include all possible Keys it's just whatever the the the working set is whatever the the latest changes are that you've made and at some point when the M table gets

26:25 full then we're going to convert it to an on disc data structure called the SS table that basically going to convert that inmemory data structure into log records and then that's going to get written out the disk and then we'll see in a second over time we start accumulating these these these SS tables we need to start compacting them because we have redundant information uh and then that'll that'll sort of speed things up and reduce amount of space we're storage

26:50 amount of storage space we we're we're consuming to keep track of these records so let's look at high example so

11. LogStructured Merge Trees Example

26:56 again we're going to have the dichotomy between memory and in dis and then we'll have this m table that's sitting in memory this is a what I'm showing is generic data structure right uh in Rox DB they're using a skip list all systems use Link list you could just use a b B+ tree or try right it doesn't matter it's some tree structure where we can keep do you look up some keys and get

27:21 values so if the application comes along and it wants to do a right so again we can only do puts and deletes what's talk about read in a second so I want to put key 101 and assume this this one key 101 is like some again like almost like the record ID but instead of being a page number and a and a slot number like it is in postgress it's more like a synthetic number like an oracle or uh sorry in SQL light where it's like it's some monotonically increasing counter

27:46 right there's some counter getting incremented by one every time you want to reference a new new key so I want to S uh do a put on key 101 into A1 and then assume my M table has some you know the data structure has some existing guideposts but down here in the leades this where I actually want to store store data so I'm gonna pen a new record that says or add a new entry into my data structure that says here's for key 101 here's the new you know here here's the data for

28:12 it then now want to do a a put on key 102 for add a new value or install the value B1 for it so in this case here I again I I I put a new Leaf entry in my my M table so now if I do if I do another put on key 101

28:28 I would always check the mem table to see whether that key exists in this case here we we just inserted key 101 so all we would do now is just update its entry for it so because it's in memory it's fast it's it's cheap to do in place updates so we're allowed to do in place updates for what exists in memory here so that's

28:47 fine then now I do a put on 103 add a new entry here and now at this point say my M table is full right this is a trivial example because has to fit on PowerPoint but say I Can Only Store three entries so now I I need to spill my m m table out the dis allocate new memory for a new mem table that can absorb new updates and then in the background I'm going to write this m table this mem table out the dis so I'm going to do a simple conversion where I just walk along the leaf nodes find all the the latest entries for the keys that I have sort them based on the key which I would get from the leaf nodes anyway right the leaf notes are sorted and then now I have an SS table that's going to record here's the log entry a log record for every single thing that was updated in my in my M

29:33 table and then I can blow the M table

12. LevelDB

29:35 memory away and then let it you know let it be reused for the next batch of rights that are showing up so again so the the the order in which we're going to insert them in our M table or sorry in our SS table within that single SS table itself is going to be from key low to

29:53 high and then we're going to write it out to to disk and the what I'm going to show here is what Rox DB does and level DB does most common approaches you sort of have this notion of levels and think of like a level within within you know B+ tree or B tree right the idea is that we're going to slowly move data down uh and and create larger SS tables as we go from one level to the next so at the very beginning we just insert our new SS table on disk at at level

30:22 zero and let's say now again we we keep keep running there's new me tables get created they get converted tables and I keep appending uh new SS tables to level zero we're still going to order these from from from newest to oldest going from from left to right in my example here so now at some point level zero is going to get full right we have too many SS tables and we need to start compacting them and we're going to push it down to uh to level one right the idea here is that we're going to find a bunch of s tables that you know either all of them within our level or things that that are are adjacent to each other in time and we're going to do a basically a sort merge find the latest entry for different keys that we have

31:05 across the SS tables again because since we know the order of time that that they've occurred and we're going to combine them into a new compacted SS table that's going to be larger than the one uh in the level above

31:16 us right and we just keep doing this as we we create new SS tables uh they'll get they'll get compacted and create new SS tables going down the previous level same thing now level one level one's running out of space because we have too many SS tables so we want to start combining compacting them pushing them down yes how do you how do you combine two SS table the question is how do you do the compaction of two SS tables next

31:39 slide but it's basically like I like I know the order in time so I want to make sure that I always have the the the latest version if you will of a key operation so if I if if if if I first do a put on on key 101 and then later I do a put on key 101 I don't need to see that earlier one so I can just I can just ignore the second one ignore the older one because all I care about here is the latest

32:06 version yes do we need to from to struct why his question is why can't you just take the mem table and uh just write out the dis and cize it at the dis and versus converting to this log log record stuff um

32:28 because I because I don't need that those additional sort of guide posts of like keeping track of how to go do splits and so forth I literally just have a log to tell me here's all the changes I need to make we'll talk about the summary table a second we'll talk about how to do efficient lookups on that but also tell they're also sorted based on the key so I can just do binary search to quickly find the the record I'm looking

32:52 for yes would you put in a theable would you put what sorry uh what do you put like in the node of the man table like it's a tree structure what do you put like in the single node in the table question is what what is in a node in in a mem table it's a so it's a key value pair right a it's a key value lookup so like forg key here's the value for it right and I'm being vague on what the data structure is if it's a skip list then you have these towers right if it's a be tree you have these guide noes inter nodes it doesn't matter all we care about is that the leaf noes are inserted based on key order and again it's a mapping from a key to a value

33:28 based on the put operations and then when you write it to SS table you con it to logs question is when you write to an SS table you convert logs yes you just you scan along these Leaf nodes and then you just write out like here's the keys and here's the value got put for it but like uh you got like outputs operations what if I do yeah I have all puts in in the M table no you overwrite them

33:49 because you can do in place updates because it's in memory it's fast yes are we ordering the M table as tree structure instead of lock structure just because we want to do fast lookup the question is are we ordering the the M table as a tree structure instead of a log structure because we do fast lookups

34:06 yes right the M table is going to be maybe a couple hundred Megs in size right it's not going to be you know when the levels can be like gigabytes and terabytes and pedabytes yes say it again won't scans be extensive the linear SC the linear question is will linear scans be extensive yes we'll get to that in a second but yes actually that's

34:36 next so he points out and he's correct

13. Summary Tables

34:40 so our rights are really fast now because I essentially can do uh you know blind inserts meaning like if I have to insert a new record I don't have to go find a page to go put it in maybe bring that into memory I just insert it into my M table and then some later point someone else is going to going to figure that out for me I'm also not showing here there's also a separate right ahead log that we keep for the M table so if we crash we come back we need to recover the M table from the log and then once it's on SS table written a disc we can throw that log away we again we're ignoring that we'll cover recovery with logs later in semester but so his point the big tradeoff we're making here is that our reads are really sorry our wrs are really fast but now the reads can be expensive depending on where the data is that we actually want to

35:23 read right so assume now I have I have some M table again that's been populated in memory and now if someone wants to do a look up on key 101 I first check the mem table if it's there great then I had the latest you know the the version I care about and I I get you know I can answer the query but it's not there then I got to start scanning down here to go figure out where the latest version is

35:44 and so that the the the the Brute Force thing would be start at level zero do uh binary search within each SS table to look for the key I'm looking for if it's not at level zero then go down to level one so in the worst case scenario I may end up having to scan everything which would be stupidly

36:02 slow so the way they handle that is is through what's called a summary table and it's basically additional metadata about what's in the the SS tables and the levels down below me so that rather than having to scan every level individually I can quickly try to jump to the the level and the SS table that has the key that I want so I still got to go read it from dis to find the thing I'm looking for uh but it's not it's not as bad as doing a complete squential

36:29 scan right so I could have for uh for every single SS table at every level I would have the min max value for a key and so I just know like is my key even within the range for for a given SS table at a

36:44 level if I need trying to find multiple things I can also maintain additional filters to say uh is this key with even within the level so I don't even bother looking at the minmax per key or sorry per SS table because because I got to have say thousands of ss tables per level if I can quickly ignore an entire level because I know it doesn't have the data that I want then the the filter will give me

37:05 that typically this Implement is Implement is Bloom filters we'll cover what a bloom filter is uh in a few weeks so an index will tell you like an index like a b+g will tell you for a given key here's the exact location of where that key can be found a filter is just telling you whether it exists or not doesn't tell you where it is that it just does it does exist so I can use the filter to tell me for you know key 101

37:32 it's it's nowhere it's not not it's it won't be in any SS table level zero so skip that entirely then go to level one and try to find you know do the same lookup again and maybe that's in there and I then I can do my lookup and then now even though these SS tables can be gigabytes in size uh they're going to support the ability to read the header and get some potentially index or additional metadata to say here's the offset you should jump into within my 1 gab file or where your key will be

38:02 located yes wex his question is why do you need sort mmax key for SS table if you want to range scans would you you know I want to look up all give me all the keys uh between 101 and 200 I don't know exactly what values could possibly be there so I don't want to probe them individually my my my filter right the minmax will tell me whether the the range overlaps or not

38:31 so you need both all right so this is repeat what we

14. Key Value Storage

38:39 already said so it's it's basically a key value storage approach where we're just appending log records to that represent changes to TB either puts or puts or uh deletes and delete basically you just put a basically a tombstone marker in the M table and says you know this tool has been deleted so if it doesn't exist in the M table you insert an entry and put put the tombstone marker on and say this is deleted if it is there then you just set the tombstone Mark to true and then when now you do uh writeit SS table you add a delete entry

39:11 as if you know just like a put entry right so the the idea here is that if we keep inserting tupal uh and make changes to the database we don't actually have to go look at previous records now I'm being handwavy here what the value actually is the value typically is the entire tupal

39:32 so if I'm doing Blind rights like uh I don't care what your email address is now here's your new email address then I just put a put there with that new email address and I'm done ignoring the other attributes but if I have to do things like take your age add one to it then yeah I got to do a look up go get your previous age then then then update it and do a put entry for

39:52 that but for insert heavy workloads this thing is fantastic because you just through inserting fast as you can it's basically you try to get the bare metal speed of what SSD can support yes his question is what what is the key here in the Lo storage yeah it would be like the the SE light row ID it's it's G to be some synthetic ID either coming from the application or it could be internal to the DAT system

40:29 how does the datab man system know what so question is how does the know what the key is for given Tu assuming like Tu exists that's what indexes give you right so again if if the if the primary key is based on your Android ID then to do any lookup you got your query has to say update this Android ID and now you can do look up on it if it's on a secondary value like your I don't know your your phone number

40:57 uh and even though it is unique to you it's not the primary key for the table now you need a secondary index to do a look up on the phone number get whatever the record ID is then you can then do your look up on the

41:09 storage we'll cover indexes in in two weeks all right so now let's get to his

15. compaction

41:15 question about how we're going to do compaction so again the idea here is that in the background the datab is monitors these levels it knows how much data it's writing out to this as tables and at some point there's some threshold gets triggered says this this level's too full and one starts combining them to uh SS tables and to to uh together into new new SS tables because again we can't do in place updates anytime we do a compaction we're always going to create a new SS table and then this is this is going to basically speed up

41:45 reads for us because now we're looking through less stuff potentially because we're we're removing anything that that's potentially redundant at a level and the way this is basically going to work is that we just do I'm going to show had to do this with with two SS tables but obviously you can do those multiple SS tables and they're already sorted in key order right that was the guarantee when we rot out the disc so we just do a sort merge algorithm where we just have an iterator go through each uh SS table that we're merging just do comparison to see whether they talk talking about the same key and then if yes then you always pick the one that's the

42:16 newest so if I want to merge these two SS tables assuming that it's going from newest to oldest so this one's newer than this one so to doe to compaction I basically want to have an iterator go start this here and this here and do a comparison and see whether they're referring to the same key and then again pick the one that's that's the newest so at the beginning here this is talking about key 100 key 100 is less than key 101 so I don't I know there can't be a reference to key 100 on this side here

42:43 so I can just ignore it and Skip down and I'll just write it out so just doing that process you you you you identify that the within the first SS table I want all of these entries but in this other one the second SS table here I can ignore the first three because there's referring to key 101 102 and this delete one 103 because I have puts for these all these keys on the newest one so so I can ignore them this has a put to key 104 key 104 isn't reference in first SS table so I I want to retain that in my new SS

43:17 table all right and you know whether or not you sort of combine them together and go down to the level or you combine them and keep it keep at the same level right there's different systems do different things uh and there's pros and cons for each of

43:34 them yes for look you mentioned about R right at particular level and I have like let's say seven TBL on that Lev so do I I need to a r scan on all of them right some some yeah this question is I I I don't want to bring range can you that cuz is like it's kind of higher level up above but the question is if I have to find Keys within a given range uh does that mean that within a given level uh I have to look at all the SS tables at that level yes but so that sucks don't do that and you'd want a secondary index to handle that for you to tell you exactly here's the key you should be looking for and where where can you find

44:22 them we we'll cover that later yes how often should I mer table question how often you should merge that table it depend this is a cop out answer because but it's you're gonna hear me see this multiple times at the semester it depends what does your data look like what does your workload look like what does your Hardware look like there's so many different factors involved uh it's it's there's no one like one uh prescriptive recipe I can say this you always do this and Rox CB has so many different knobs that you can tune to to figure this all out and no one can get it right it's very hard to do

16. RoxDB

44:59 okay so log seure storage is way more common now than it than it was in the say certainly in the 90s when it first came out but even the mid 2000s right and part of this is because roxb is is so uh so widely used now in a lot of different database systems so

45:19 the Rox wasn't the first so Rox DB is a fork from face that Facebook made of level DB levelb came out of Google this came out of the from Jeff Dean and and the big table project um you'll we'll cover this next week but the very first thing that that Facebook did when they Fork Rock DB sorry the very first thing that Facebook did when they forked level DB and made roxb got rid of map right because Google was letting the Opera system man in Pages that's a terrible idea Roxy B rewrote it correctly uh and and have their own buff manager which is Project one uh but there's a lot of systems now that rely on rocks DB as the key value storage like the internals of the system and then they buildt a larger

45:57 more complex you know databas system on top of that right this is how uh like cooch GB first got started was using Rox DB and Rox DB is an embedded Storage storage system so just runs inside your process uh but then DB buildt a distribute architecture around it right

46:14 and then the neon talk we had last week maybe this didn't come out exactly but the the thing they did was they ripped out the the T oriented storage of postgress like the the the the heat files and so forth and replaced it with a distrib a log structured

46:28 system and then now it has and they have a way to you pen the logs and then they have this page server that when PR requests a page because the rest of the system is assuming that it's dealing with you know heat files and and and pages in that manner their their log structured storage system basically U creates or materializes the pages for postgress in the way that it wants it from the log

46:51 records so the downsides of this approach is the big one is going to be right ampli so meaning if I do a single WR to a record then it's going to end up getting Rewritten into storage multiple times over the lifetime of that tupal right because if I if I insert it uh and LS an M table it goes in the first SS table then it gets written on the dis and then eventually it's going to get compacted and gets written again to the next level

47:19 so for one write to a to a tuple I may end up writing it out dozens of times hundreds of times and depending on what Hardware I'm running on I'm either going to burn out the SSD or if I'm running on Amazon I'm I'm going to pay for that that operation that up that right operation right again there's no free

47:37 lunch so that's a downside versus the 21 storage with a slot of pages if I do an insert to a tuple it lands in that that page ignoring all the vacuum stuff from postgress then it just it's going to live there for for the life of the database right it never never never has to get Rewritten

47:54 out thatum complicates things but we'll cover that later and then compaction is obviously not cheap right so so the idea is that my my my inserts are really fast because I don't have to do any reorganization of of data to insert new records but I'm going to pay that cost later on because then compaction got to run in the background to sort of clean clean up clean things up so again there's no free lunch in in this in the twoo architecture I do my insert I'm done now depending on how I'm organizing

48:24 my my my data structures I may have paid an up front Colum to reorganize that data structure in order to do that insert but then later on the reads are cheap whereas in in log structure storage is the

48:40 opposite all right so

17. Index Organized Storage

48:44 the I've been dancing around this this idea of indexes a couple times now you guys have asking good questions like this like Hey how do you actually find things or how do you find things if you don't have the the record ID how do you get the record ID um

48:58 and the we've been talking about this idea of these indexes and we don't really need know what the data structure is but the idea that it's basically this associate array that for a given key I can give you back that value and that value is going to be the typically the record ID and then with that record ID I can then go to the page directory or the table summary within uh you know if it's if it's in log structure and then go find where the actual tool was actually being

49:22 located so what if instead of having these auxilary data Str these indexes to that I can use to find the data that I want what if this the data structure itself was the table so that when I do my lookup on the index when I land in the leaf noes it's the data that I

49:42 want so this is called index organized storage and the basic idea is that the the leaf nose or whatever data structure I have or it's a hash table the the the buckets within my hash table instead of being a record ID value that I then can do you know look up in the page to find what I want the value within the data structure or the index is the is my tupal so there isn't another step I need to do I land exactly where the the the location has the data that I

50:13 want so this approach is is more common in the 90s uh and maybe early 2000s uh less common now most most of the new systems are going to be log structured um but it's again it's the opposite of log structure log structure merries loog structure storage where I'm paying the cost to maintain the index when I do my updates either inserts or deletes but now my read are going be really fast where log structured it was you're paying it later so the basic idea is assume I have some tree data structure

50:45 say this is a B+ tree which we'll cover in a few weeks could be a try it could be skip list it doesn't matter and then the leaf no is going to be sorted based on the key so the the the inner nodes will just guide posts that just tell us how to go left and right and do splits Leaf nodes are actually actual the tals themselves so now the pages where I'm storing my leaf nodes are going to be the almost exactly like the slot of page we had before but instead of having the slotted

51:13 uh the slot array be unordered uh my offset array within the page more like a slot array but just the offset to it that's going to be sorted based on the key that the index is based on so now when I want to do a lookup to find a uh find a record based on that

51:32 key I Traverse down to the to through through the the data structure to my leaf nodes I get the page then I do binary search on the on the key themselves within that that first array in the header then I can jump to the tub that I

51:50 want this is a gross simplification of how it works like we'll cover this in more detail when we talk about B+ trees right but that a high this is how this is how seal light and my seal work in the case of like uh seal server and Oracle by default I think you get I know in Oracle you get by default you get Heap Heap files in Seal server I think you get default Heap files might as well but you can say like create table and tell to be in this organized and it's going to set it up this way so the the high-end Enterprise systems can actually support both heat files and indexes or index organized storage and just like before in a slot of pages the T grow from the end to beginning and then the offset array grows grows from the beginning to the

52:31 end again it's it's a different way to organize uh data uh and there's pros and cons to to both to all three different approaches right you have the two architecture log structure storage and then index organized storage all right

18. What is a Tuple

52:48 so we've been talking about how to organize tupal now it's time to talk about what the hell actually is inside of a tupal and so a tubo is basically btes it's a sequent of bites with typically a header at in front of it that tells you something about what what those bites are not necessarily the schema right like it you know this offset within the bite array is going to be this type of this size right all that's sort in the catalog either in the the page header or in separate separate pages but there might be some additional metadata we'll cover throughout the semester that you can store in the header

53:27 and so what the data system's job at the end of the day is doing is it knows how to interpret that bite array to mean whatever it is the data that that you want it to store like the types and the potential values and whether they could be null or not the end of the day it's just a bunch of btes and a bunch of files but the data system is imposing structure and and knows how to interpret that that those btes to give it actually

53:53 meaning so say we a really table simple table Fu it has two two values uh ID is a a 32bit integer and value is a 64-bit integer and again it's just an unsign unsigned Char array of some size at the beginning we have a header different Data Systems have different size headers because they store different things doesn't matter and then now we have in the first bite sequence it's we have all the the ID values the bits for the ID and then all the bits for

54:24 Value so again when now my query wants to say okay give me for this tupal knowing how I got to that tupal or got you know got to this bite sequence if I want the ID value what you're essentially doing is knowing where the tupal starts you know the size of the header because that's going to be the same for every single tupo and I do simple you know arithmetic to say okay

54:46 the header plus what offset within my my table is going to give me the starting location in this bite sequence or where where this value will begin and then now I'm just doing the same thing as reinterpret cast to take arbitrary bite array and put it into the type that I would

55:01 want I'm showing you how to do this in in C++ but the idea is the same for other languages that's it data is just bits or just btes of course it's not always that easy right because things can go wrong when you when you have to store a bunch of different uh attributes

55:19 together

19. Architecture Details

55:21 so without going to a little architecture details uh CPUs modern CPUs want things to be nicely aligned in in some word size so modern processors it's typically 64-bit words uh sometimes you would care about keeping things within a 64 by cach line but for Simplicity it's assume that we care about 64-bit

55:43 words and so the da the the CPU is going to want software like your application or your database system to access data along these 64-bit word boundaries so the problem's going to be now if someone creates a table and has these mixed types that don't nicely align to those those boundaries we have to do something because otherwise it's going to be really slow so let's see an example here so now my table has more attributes so the first thing we have is a 32-bit uh ID field right and again assuming you have 64-bit words I can pack that in the first 32 bits of of the first of the F first

56:21 word then I have now the the time stamp well that's 64 bits all right say say it's storing things in milliseconds but now my my my creation date for this tupo now the first 32 bits is in the first 64-bit word and the last 32 bits are in the the second

56:40 word all right and then going down for all the other attributes uh you know they're going to see we're splitting boundaries so what happens now if if my database system says all right this is the tup I want I jump to uh the offset where this this bite array starts and I want the cut I want the creation date that's at this offset what happens now when I access this 64-bit value that's span across two words what

57:11 happens so he says yeah so what happens is in modern CPUs what will happen is the CPU once the CPU is trying to hide that you're stupid from you and and and will do the request you're asking for and give you back the data you want packed together aign but it's essentially you have to do two two memory or cach line accesses to go get this data and then Stitch it back together and give it back to you in older CPUs you would actually get would get a an interrupt and basically tell you don't do that that's that's wrong

57:42 it's going to be slow but x86 and now arm they'll all hide this for you so to do this look up now in in Cate is going to cost twice as much as it would if it was aligned meaning your database is going to go slower and that's bad

57:57 so how how can we solve this yes right so he says just some add some empty space yeah so the most common approach is just do padding so here I'm saying again I have I have a 32bit word sorry 3 bit integer but I have to sort 64bit word I'll just add 32 bits a bunch of zeros at the end of it and then now again my my data system has to know okay I've padded them out so when I want to access these different attributes I know how to jump to the right offset within my my bite array to get the data that I

58:34 want this is the most common approach because it's easy we could try to be clever though yes reorder next slide yes you said you reorder yes so again remember we talked about the the the the separation between the the the the logical view or the and the physical view so there there's logical physical data Independence

58:56 so logically the application wants to represent wants to get back data for this this table in this order right if I call a select star I expect to get the ID followed by the date followed by the color and by the ZIP code but underneath the covers we could actually reorder the layout of of those attributes in our bite sequence so that we can nicely pack them in into our into our bite array

59:20 right so we can just move the the creation date over to start at you know over here and move the ZIP code over there and move sorry move the the color over there and zip code back over here and then now we're nicely packed into our

59:33 uh into our you know into our our boards we still have a little extra space at the end because we don't want that the next Tuple to start in the middle of of of this word so we still have some padding at the end we may not always save space in this case but again we we avoid having to access things across uh word

59:52 boundaries right the padding one is actually the most common um let me see we have a little bit time I can show you can post real quickly so postgress postos has this nice uh function called row where you basically say you can give it an array and it it creates a you know a single two before it and then they have a another function called PG column

1:00:31 size where you can get back the number of bytes that has to use has to store to represent that data so here I'm saying I have three values one 2 three and the size of it is 36 bytes uh because it's it's uh I think it's storing them as what what is

1:00:51 that there's some overhead there um but it's you know it's it's it's representing the bytes with some extrait metadata for like the Header information but it's basically a compact size it but then remember I said you can do casting so I can take I can add the colon colon at the end of all the values

1:01:10 and I can cast it to a type and then here you can say I want to downsize it from uh from from uh 32-bit integers to 16 bit integers uh represent as two bytes and now my size is down to 30

1:01:28 so if I do something like this so I I have a bunch of you know a bunch of different data together so I have some chars I have some integers uh mixed up in one ordering PR is going to say that you can get it it'll store it as 48

1:01:45 bytes but if I just say take the same columns and reorder them differently then post doesn't have to PAD as much and get it down to 44 bytes so this exposing a way to identify that postc is doing some padding based on the size of the data that I actually want to store and one's going to be more optimal than another yes this already

1:02:09 ped question is is the four bytes already P at the end for this uh in sake of time let to walk through it we take it offline there's a way to dump out like the bite arrays as well we can look at that afterwards

1:02:29 yep okay s right so so we know that it's starting things as bite arrays now what what are the actual bits of the interal attributes so depending what the type is you'll see uh there's a bunch of different ways to approach it so for

1:02:47 basic integers so 32 bit 64-bit 8 bit 16 bit integers it's just going to use the same thing that's in C C++ right when I create an unsigned INT in in C that's essentially what post is doing under the cover every D syst is doing under the cover for for decimals we'll come back in a second but there's two approaches to that one could be the the the the i e 754 standard for floating Point numbers

1:03:14 but that's going to have rounding issues but then every single data system is also going to implement uh fix Point decimals and where they're going to maintain some extra metadata about the decimal you're trying to store so that they can avoid all the rounding errors that the the harbor will give you for varchars or or any variable length data or large data like text and blobs typically there's going to be a header for the the Tuple in line with the rest of the data sorry the attrib rest of the data we'll see in a second

1:03:42 that says here's the size of the data and depending on how big the data is you're actually trying to store for these fields it's either just in line with the rest of the data or you have a pointer to some other page look like another record ID that says here's the here's the the data you're actually looking for for this

1:04:01 attribute we're not going to talk about cations and sorting but we also need to maintain metadata for storing strings of how you actually you want to sort them right is it Unicode is it some Japanese character ET some forth time stamps uh can be stored in different ways but one of the most common ones is just storing the the number of milliseconds or microsc since the Unix Epoch um there's time zone stuff you have to maintain as well it is more complicated but yes what happens

1:04:31 Str this question is what happens if a strings larer than than one page you overflow we'll we'll come to that it's just a pointer to the next the next chunk of it all right so I want to talk quickly about the the numeric stuff because again this is if you're used to writing C C++ code then you may not realize how

1:04:53 how inaccurate floating Point numbers actually are and from a database perspective because we're trying to be the system of record for major organizations and applications these rounding errors are problematic and therefore we want to make sure we do something

1:05:06 correct so again the I74 standard basically specifies how harbard should represent the bits for floating Point numbers and then what you should do if you add you know different floating Point numbers together what the result should should look like be represented as and again if you call in in you know get a float or a double in C plus you're getting the the i e 74

1:05:28 standard and these me really really fast because modern CPUs have instructions that know how to Crunch on these 754 floating Point numbers very quickly but again because they're not supposed to be they're not guaranteed to be entirely accurate you're going to get weird rounding errors that could cause problems so if you write a really really simple C code like this that takes two numbers two floats 0.1 and 0.2 add them together just print out the value vales

1:05:57 it'll look correct just by the default print F statements but if you actually extend out say give me all the the the the the bites for this floating Point print those out now you see there there's some weird issues here because the haror can't exactly represent the the decimal 0.3 or fractions like

1:06:18 that so for simple things maybe not a big deal but for like you know sending Rockets up to the moon or it's your bank account and you're calculating interest you don't want these rounding errors because people are going to notice and there's going to be you know real world

1:06:33 problems so most data system are instead give you uh also provide these these fix Point Precision numbers uh usually represented as numerics or decimals in the case of Oracle actually think if you call if you say I want a uh you want a float type they're always going to give you uh the fix Point numeric instead and they've done a lot of optimizations that make it look you know make go really really fast

1:06:56 so there's bunch of different ways to implement these things but at at a high level think of like we're just storing almost the string of what the the the the Bice sequence of what the floating Point number actually is in its like full correct form uh and then there's going to be some metadata says here's where the decimal point is here's what the sign is here's whether it's it's infinity or not this extra metadata we going to maintain for that value that we then have to use to interpret what that string sequence actually means for for the real

1:07:27 value so you can go look at postest uh you can actually look in their code and find what they're actually doing so this is their numeric type so you see that there's a bunch of again metadata to store one floating Point number they're going to keep track of the number digits the weight the scale the sign and then there's this type def here that says for numeric digits and that's just unsigned Char that's just the string of of what the decimal is then at run time again they use this metadata to to interpret

1:07:55 what that means to generate the real floating Point number okay so that's great but is it fast or slow well again it's going to be slower than the hardware because there there isn't going to be single instructions to to to add these numbers together uh again you go look at the post code this is just to do add right and you see all these these if then El's in the switch statement here for the different Corner cases of trying to add

1:08:20 two numerics together where one one might be negative one might be you know infinity and so for and there's no way that any of this is going to be as fast as as you know floating Point number plus floating Point number in the hardware but again that's a cost you pay to have uh to have the the exact exactness of

1:08:41 numerics and so I'm showing numerics as one example here but like there's a bunch of different data types that data provide that are going to basically work the same way numerics is the easiest one to W wrap your head around specialized

1:08:54 support num the question is are there specialized haror to support numerics of of databases yeah no right postest is open source they're not fabbing any hardware Oracle uh because when they bought Sun they bought they got the spark stuff they used to put their own Oracle database instructions in the ISA

1:09:13 uh so that you know if you ran if you bought their hardware and ran their database it ran really really fast uh they don't do they don't sell Sparks anymore but companies have tried to do that before yes we'll cover that we'll cover specialized Hardware later in the

1:09:28 semester it of us never works out no because I think about like by the time I if I make a specialized chip ignoring gpus right and fpg that's different because that's commodity stuff but by the time in the 80s people were trying to they were called database machines they would make specialized Hardware to accelerate the database in One Way by the time you designed fabed and then shipped your your specialized Hardware you know Intel put out the new version x86 and any you had were lost uh

1:09:58 every people try every every 5 10 years that it never works out gpus and uh might be problem GPU is getting data in and out some some companies have solve that we'll cover that later in the semester all right so next thing we got to do is how we're going to represent nulls so the most common way to do this in in a row store which will distinguish between row store and column store next class but in that header for every single Tuple right you're going to have this bit map that just says for for my for the attributes that are in this tupal for the colums that are in my tupal the bit is set to one if the value is actually

1:10:34 null and so I'll still store empty space in my Tuple because I don't want to have specialized code that has different you know how to jump into different offsets based on whether the bits are null or not I'll still retain the space for for the for the empty value or the null value because again if I do if I do in place updates I may go back and put a new value in to overplace null but I'll I'll check that bit map to say yes is this thing null or

1:10:59 Not Another approach is you use special values or placeholder values where you just say there's some value that that if I see it then I know that this Val this Tuple or this attribute is be set to null so one might even be if I have 32-bit integers if I set the the tupal the attribute value to in32 Min like the smallest number you can represent as an unsigned 30 bit integer then then if I ever see that I know it's null now that means that nobody can ever insert that value I have to check that in the higher parts of the system and throw an exception if they try to do that and say it's out of range but now I just know if I see that value then I I know it's null

1:11:36 we'll see this next class this is actually the most common approach or more common now in in column stores because it's just it keeps everything nicely aligned when you want to start doing uh fix fixed length offsets the last approach is to on a per attribute basis you actually store some an extra bit to say like as a prefix to the value and say this value is actually null so instead of having the bit map in the header you basically have a bit that but the bits are stored in front of every single uh

1:12:08 attribute what's the problem with that yes doesn't use a other it doesn't use a hold it messes up your alignment right if I'm trying to store a 8 bit uh Boolean and I have to keep track of it's null I have to store is nine bits because I need that extra bit to keep track whether it's null I got to pad it out or or represent the bit as a whole another bite so now my 8 bit bullying

1:12:35 becomes 16 bits right so I only know one company did that did this msql and then uh I think when they rebranded single sword they got rid of this I only bring this up just to tell you like not to do this I'll try to do this this semester like this exists people do it don't do this it's stupid right if you if you're doing a row store the bit map header is the way to go if you're doing a column store special values is probably the right way to do this some aemory databases to reduce memory footprint instead of sing the bit map they would store the extra value so the placeholder value because it reduces space yes why is to have

1:13:11 dat single so why is it why is it necessary to use a null per data type for different data tyes like this question is like for integers I'm setting it to n32 Min what in that case again if it's a 64-bit

1:13:31 uh if it's a 64-bit number I want to use a 64-bit mint not 32bit mint right it's some bit pattern that that that it's that's meant to represent and we just use we just haveen to use that one because it's you use the minimum one because it's like it's unlikely someone's gonna want to set it to that so does that mean two attributes of different type even though they both are not his question is it means the two attributes of different types even though they're both null are they not

1:13:59 equal do you mean physically or logically cuz logically null doesn't equal null n logal logical null does not equal null right uh so select if I go null equals null null right but if I do null is null

1:14:31 true null does not equal like does something does unknown equal unknown unknown right does null equal one unknown right it's not a null pointer and we think about in like C it's like I I don't know what's in this therefore I can't reason about what's in

1:14:51 it yep now your question is so that's logically physically no because the bits the bit sequence will be different all right so I say this seems like a a l level detail uh that like people maybe figured out long ago but we actually wrote a paper about it um this I mean just last semester with one of my former students back at shinua and his student we have a paper on nulls uh which it's always

1:15:19 exciting and it's the spoiler is again the second one is GNA be better for uh for column stores which we'll cover next class all right so now this this come up a couple times now how do I handle large values so all database Sy as far as I know most datab systems will not let you store a tupal if the size of the data that's inlined in the sort of say the primary page of it exceeds the size of a

1:15:43 page so again so post say 8 kilobyte pages I can't store you know a billion I can't make a table with a billion columns because that won't fit in a single page but now some values may exceed the size of that page and I need to keep track of that and then allow them overflow into auxiliary Pages or essentially called overflow pages so the idea here say a table I have three columns has in two integers followed by a text field text basically unbounded V varar right can be any arbitrary size so

1:16:14 if the if the text field I'm storing is small then I can just store that in line with with my my tupal my regular tuples in the page things are fine right but if it's really really big then what I wouldn't instead do is have an overflow page where the inline attribute that I'm storing with the rest of the data like the the the the called the bass tubal if you will that's now going to be this size and this location which is now a pointer to this overflow page so now if I'm scanning along and I'm trying to read this Tuple and it says okay I need to read this text field or the contents attribute I would come across this the size in the pointer then I got to go follow that pointer to go figure out where where the actual value is

1:16:55 and then his question is well what if this thing exceeds the size of the page just add another pointer to overflow and say Here's here's the rest of it yes this question is VAR binary started the same pattern VAR bar uh VAR Chart 2 and Oracle blob there's a bunch of they have different names yes anything that's going to be really big you do this

1:17:22 question what the store the exactly same like the paddings or like the size locations into that bar so this question is what if I create a column called size and location and try to I meaning theing the binary data which happens to have the like the same structure of the size and loation

1:17:56 his question so his question is um what if someone stores basically whatever the struct that post or whatever say maintains about here's a size and location what do they have to store a blob that is that well because there's this is like a

1:18:14 header down it's gonna first four bits or sorry four bytes is going to be the size then a FL say is this thing in line or is it going to an page so it doesn't care what you're storing it's not going to interpret your bites and do anything like you can't like that's a huge security hole you would definitely not do that it was another

1:18:38 question so there's a lot of optimizations you can do with this right because this overflow page isn't like a regular data page right in some cases I I my if I run my query where I only need the first two columns and I don't need the third one I don't have to read the Overflow page all right so in the case of post grass and other systems you can actually compress this with like zzip or Snappy or Z standard we'll see next class like you actually compress this on

1:19:02 dis uh and and you know uncompress it when you bring it back in uh because you know it's bunch of text field it's going to compress really well we won't cover this in in this class uh we cover this in the advanced class there's another technique called German strings where if I know it's a varar and instead of just storing just the size of location what if I also store a prefix

1:19:25 May the first eight btes or of of whatever is in this varart piece so now if I'm trying to do matching like find me all the you know find me all the the email addresses to start with you know paav I can just go look at that prefix in my header uh back in the inline data because I have to fetch the whole tle anyway check that prefix if it doesn't match then I know I don't need to check the Overflow page right not very many systems do that it's more common in the newer systems um it was invented by the Germans I didn't know what to call it so I called it German strings and then they that's what they use now I can send the blog article later um but there's a bunch of things you can do if you know things are meant for overflow reg than regular data Pages all right we're well over time I was going to finish up

1:20:06 quickly for really really big files you actually can store them on the local disk and then now the data system just has a pointer to to that like a like a URI that says here's where this is now because the data system is not managing those pages is managed by the OS file system all the guarantees that we provide for for data for for that we storing in the DAT system those are out the door and there's a bunch of different types that do that for

1:20:30 you okay catalog we can cover next class basically it's a it's the metadata we keep track about our data right all right so finish up so we talked about the log structure storage and index organ storage organized storage these are these are alternatives to storing storing data

1:20:52 um and the you know there's pros and cons to each of them for right heavy workloads the log structure storage is be great because I'm maximizing the amount of squal iio because it's just writing up the giant SS table all at once or compac and writing out all at once whereas like the index organized storage or the Heap storage it could be R most of random rights and the storage manager although we said there's the abstraction layers that we're trying to hide from the rest of the system through apis is not entirely going to be true because when we start about transactions and Recovery we need to expose some metadata about what we're doing up above to what comes down below and vice versa

1:21:27 all right so next class is going to be about different storage models so this is going to break how you've been thinking about databases probably all your life where you have a bunch of rows uh and all the data is contiguous for a given attribute ignoring the Overflow stuff so now we're basically going to take that row storage model you have in your mind and flip it and store everything as columns instead and see what the pros and cons of that approach is okay all right see you on Wednesday I need something refreshing when I get finish man fessing to cold a whole B like Smith and Wesson one court and my thoughts hip hop related WR a rhyme in my pants intoxicated lyrics are quicker with a simple Mo licker since on my city slicker play waves are picker rhes I create rotate at of R to quick to duplicate feel a breeze at a skate mik at fah when I hold real then I'm in flight then we ignite starts to boil I heat up the party for you let my girl R me my mic down with oil re still turns

1:22:25 with third de burns from one man I heat up your brain give it a suntan so just cool let the temperature rise to cool it all with same odds [Music]