CMU Database Group · 1:22:27 · https://www.youtube.com/watch?v=dSxV5Sob5V8
1. <Untitled Chapter 1>
0:05 Official members bounce. Bust off the chrome. Realize it's real hell where we call home. Official members bounce. Bust off the chrome. Realize it's real hell where we call home. All right. So, as I said last class, uh today and going forward rest of the semester, this is where we start talking about what the internals of a database system look like. Um so, we're talk Today, we're going to start at the very bottom with files and pages on on disk.
0:41 Um before we get to that though, uh just go through what's uh what's due for you guys right now, right? Homework one and project zero are due this Sunday at at midnight. Um I think about I think I checked this morning about 100% or 100 out of 130 people have completed project zero. If you haven't started project zero, please get started now. And then homework one, again, it's not meant to be very taxing, but you write some SQL queries in DuckDB and SQLite.
1:06 Uh that's also due at the same day. And then so, starting next week, uh on on on Monday, but maybe Tuesday, we'll release project one. And this one is actually for a grade, and this will be implementing uh a buffer pool manager, which we'll cover uh in in a few lectures. But we'll we'll get it out early. By now, since you have you completed project zero, you've already set up your your development environment to write code locally.
1:28 So, that shouldn't be an issue for anyone else. And so, you can start banging on the code right away. So, any quick questions about homework one or project zero? Who has not started project zero? Good. Awesome. Every year, there's always somebody. I'm glad to hear that nobody is waiting that late. Okay. So, right, last class was the we talked the relational model and relational algebra, and and then with SQL.
1:54 Um and that was just to understand what we what the application is going to see in the database at the logical level. Um they write SQL queries that hit up against tables. Um and so going forward, as I said, at this point we're not going to go revisit the relational model except to understand how we actually implement something that can support it. So we have to understand again what the application is going to see and then now we'll start designing a system that can provide that logical view uh for in a database.
2:21 So the overall outline of the course is as follows. Uh so we've already covered relational databases. Again, that's the logical level. And then going down here, it's a bunch of the different layers of the system. And we're going to go in reverse order from from how the system is actually implemented. So we're going to start at the very bottom, like at the disk layer, the storage layer, and then work our way up. And you know, talk about query execution, cursor control, all that stuff.
2:42 Um so you can sort of think that the conceptual database system we're going to be building throughout the entire semester is made up of a bunch of layers. Right? It's a very common approach in in computer science and in software development that you abstract away the details of different parts of the system
2:58 and you just expose some kind of layer that has an API that is that the layers above and below it can can interact with. Right? The operating system provides this, applications provide this. So our database system is going to work basically the same way. So again, at the lowest the lowest layer will be the thing that actually talks to a disk or non-volatile storage as as I'll explain in a second. Then we'll bring things in the memory, the buffer manager.
3:19 Then we'll expose a way to get access to the data we bring into memory through access methods. Then be a way to execute queries and then lastly be a way to actually take a single query and plan it. So the application is floating up above here, right? And it's just going to send us SQL queries. And then it's going to basically tickle all the parts going down the stack to actually execute queries. In some cases, all your data is in memory, so maybe you don't go to the disk manager.
3:43 Uh but you know, you don't want to always assume the case. So as I said, today's class and for the next two two lectures, we're at this part here, the storage level. Like what does it actually do the data bits actually look like on disk? What's inside of the uh you know files on disk? What do tuples actually look like? We're starting at that lowest level and then again, we'll work our way up. So, we'll we'll first provide some background about again what what it means to have a disk-based database system or disk-oriented database system.
4:09 Then we'll talk about what the files look like, what the pages look like. And again, we're going inside now. You know, a file is made of pages, pages has uh has tuples inside of it. And then we'll talk about what the tuples look like. Next class, we'll talk more about like what actual the layout of the bits or the bytes within actual attributes in the tuple look like. And then as I said on on the first lecture, uh every Wednesday we'll have what we call a flash talk.
4:30 So, today will be Neon. Uh what He's a former Postgres developer, the co-founder of Neon. He's going to come give a 10-minute talk about here's what Neon is, here's why it's interesting. And you may not understand everything he's going to talk about, but as we go throughout this semester, you know, a lot of it will start start to make more sense. Okay? So, we'll try to stop at 3:10 and then we'll switch over to him uh on Zoom to get to give give the talk. Okay? All right.
4:54 So, this semester we're focusing on what I'll call a disk-based architecture or disk-oriented database management system. What this means is that we're going to design the software inside of our database system to assume that the primary storage location of data of the database that we're managing in our database management system is going to be on non-volatile disk. Right?
5:17 And so, what the system is essentially doing for us is orchestrating the movement of data back and forth between non-volatile storage and memory. It's a classic von Neumann architecture, right? You have you have storage, you have some kind of disk thing. You can't operate directly things on disk. Not entirely true with some modern hardware, but we can ignore that. But you can't operate anything on disk, you got to bring it into memory. Then there's this thing called the CPU that's going to do some computation on it to to manipulate the data or get extract answers that you're looking for.
5:46 So, our whole system, the entire semester really is built around this key idea here that we got a bunch of things on disk. We got to bring it into memory and to to do what to process it. And the tricky thing is going to be as we see as we go along is, okay, but I write something in memory, how do I make sure it safely lands on disk? Right?
6:02 That'll be a whole another uh uh you know, several lectures discuss how we're going to do that. But for now, let's assume we got something on disk, we want to bring it into memory, how do we do that?
6:12 So, the way to think about now the hardware that we're going to interact with and we have to support in our in our data management system is typically through this hierarchy like this. And I'm sure you've seen some kind of variation of this in in other classes, but the way to sort of think about this is that at the at the top level of the of this hierarchy, you have what's the most fastest thing you can have, a CPU register. Right?
6:30 There's only so many registers in the CPU. That's the fastest thing you can access data from in in your CPU. And then below that, you have CPU caches, DRAM, like you know, uh like memory, SSDs, spinning disk hard drives, and then network storage would be like a distributed file system or if you're on Amazon S3, something like that, right?
6:51 So, again, this this this hierarchy is not is not novel, not that interesting to by itself. The thing that we care about in this class is understanding how the things get slower and faster and smaller and larger as you go up and down the stack, and that's going to determine what algorithms, what data structures you're going to use to maintain data at these different levels. Right?
7:11 So, at the lowest level, things are really big, a lot slower, uh but a lot larger. Like S3, for my purposes here, it's infinite storage. Right? At the obviously there's a limit because there's only so many physical drives at Amazon, but like your your credit card will run out of money before you can store enough data there, right? But at the very very top, it's CPU registers, right? Those things there's make maybe a couple dozen of them, depending on what CPU you're using, right?
7:36 So, we have to understand like if as we move data back and forth, you know, what tier are we at, how's the data actually should be accessed, and how much can we actually put into it. And that will determine again what algorithms we may may want to choose. This division line here is also very important to us because anything above this division line is going to be volatile.
7:53 Meaning if I pull the plug on the machine, whatever's being stored in there is is gone. Right? Not as much for DRAM. I think the studies show if you pull the plug on DRAM, it lasts for like 30 seconds before the charge runs out. But for CPU caches and everything else, like it's all gone. Right? Anything below this line is non-volatile. Meaning like if I have an SSD, or if I write some store if I write some data there, we'll discuss when the hardware lies to you, but it comes back says, "Yes, I stored it for you."
8:17 You pull the plug and you come back, it should be there. Right? The other key difference is that anything above this line is going to be byte addressable. What does that mean? Means it's in the name. It's addressing bytes. So So what does that mean? I can jump to any offset.
8:36 Sorry, yes, go for it. Like the smallest unit of memory is a byte. He said the smallest unit of memory is a byte. So what does that mean? If you want to query something from a multiple of a byte. He said if you want to query something. I'm using the word query cuz that sounds like a SQL query. But like if you want to access something, the the you can access it at a fine grain at a byte. Right?
8:56 Not entirely true cuz there's cache lines, but like we we can ignore that for here. Um and then block storage would be what? Like an SSD, I can't go get like it's some random offset just give me 64 bits at this offset. I got to bring in the whole page at at a block, which would typically be 4 kilobytes. Right?
9:15 Just to access a small small piece of it. And again, that's going to determine what data structures what algorithms we're going to use depending on what you know, what uh what how how it's addressable, how to get access to the data. Right? So now, again, this is the canonical classic hierarchy you may may see.
9:32 In modern hardware, the lines are starting to get kind of blurred. Right? So like you have uh All right, so sorry, before we get there. So, for this for this class in this semester, we're going to refer to anything that's in DRAM as just memory. Right?
9:45 We're going to ignore CPU caches and all that. That's in the advanced class for now. Then anything below this what is called disk. Right? Whether it's S3 or an SSD or a spinning disk hard drive, I'm just going to say disk, assume it means something down here.
9:58 As I was saying, where the lines get blurry is you have things like fast network storage where it it's not it's not local to you, but you can access it pretty quickly, and it may be durable because you don't actually know what you're writing to. Right?
10:12 Like networks are getting much faster than the CPUs these days. Then there's this other class of storage called persistent memory. Who here has ever heard Optane? From Intel. One, two, three, right? What happened to it? Does it still exist? No, it's dead, right? Um Intel is hemorrhaging money, and then the new CEO came in 2022 and killed it off.
10:34 But what was amazing about this was it was specialized hardware that that sat in the DIMM slot like DRAM, but if you you pull the plug on it, it would actually retain whatever you're storing. Right? So, if had Intel not killed this off,
10:49 a bunch of these lectures we we talk about the buffer manager, a lot of that goes away in this class because no longer are you moving back and data back and forth between DRAM and disk cuz this thing is just persistent memory. Right? It's not as fast as DRAM.
11:00 You got to flush things. It's a bit more tricky, right? And it can wear out. There's always issues like that, but you know, had this really taken off, this would have been a a game changer for databases. Um and we would we wouldn't be talking about disk oriented systems about moving pages back and forth. It would be about designing systems that access this directly.
11:17 Which is what an in-memory database does, which we're not going to talk about this class, but there are systems where you don't assume everything's on disk. You assume everything's in DRAM. So, if you assume everything's in persistent memory, then that that changes a lot. But like I said, Intel killed this. It doesn't exist. And what's replacing it now is this thing called CXL.
11:33 Um certain different types of CXL, but the one that we're going to care about, what we can talk about a little bit uh later on, is CXL type 3, which is basically byte-addressable memory that may not actually reside on on your physical machine. Right?
11:48 Samsung will sell you a device that'll sit in the on the PCI PCIe slot. So, it's like expanding the number of DRAM slots. You can go down the PCIe, but like the there's no reason it has to be on the same box. It could go over the network to something else. It's called disaggregated memory. So, that could be a game-changer, too, cuz now I could design a system where I'm writing to memory on CXL, but on the other side is some fast SSD, and I'm retaining things. Right?
12:10 These are This is emerging hardware. There's no real system taking a full advantage of this yet. There's no database system, but this might be a uh you know, game-changer going forward. Right? But, for our purposes, we're going to assume again, it's we have disk, we have memory. One's byte-addressable and fast, one is block-addressable and slower. And we're we're uh we'll have to handle that in our system. Another way to think about again these devices is through how fast they are.
12:36 And again, you might have seen uh something like this. Sometimes attributed to Jeff Dean has a version of this. But, I think prior to that, there was Jim Gray had a version of this as well in in the 1990s. But, it's just a way to think about the the relative performance differences between these different devices, so that again, when we design the different components or algorithms in our system, we have to know what we're actually talking to or we're going to read and write from, and we'll choose some algorithms over other based on the properties that they have.
13:02 Right? So, like at a high level, doing an L1 cache reference is about 1 nanosecond. All right, and going down, you're down to what is that? A million nanoseconds to read tape archives. Um or it's the it's a billion, sorry. Right? That's That's like something like Amazon Glacier or like physical tapes for natural backups. Nobody Nobody would store the you know, nobody would make run a database system off tape archives, but they exist.
13:23 So, if you think of nanoseconds as it's kind of hard to wrap your head around it, cuz humans don't really can't think of like that at that sort of minute measurement. But Jim Gray had a easy way to think about this is if you just change 1 nanosecond to second, now you see how ridiculous the numbers actually are and the performance difference. Orders of orders of magnitude of performance differences. And so that we're going to design our system to try to keep everything we can in DRAM cuz it's just going to be so much faster than having to go from disk.
13:48 But of course, we're not always going to be able to to do that. So the way to think of this also do is like say for instead of like reading reading a piece of memory, I want to read something from a book. If it's in L1 cache, then it's like me reading the book off this table. That's really fast. If it's like on a on in DRAM, maybe I got to walk over to the library and go read the book.
14:06 But if it's in a tape, I got to fly to Pluto to read one page in a book. All right, it's it's that much slower. We're going to avoid reading writing from disk as much as possible. But it's not always going to be possible.
14:19 Now, another key difference in this hardware that we're going to care about uh this the the storage devices is the notion of sequential and and random access. And this is going to be different than how you maybe think about algorithms and data structures in your other courses because you know, in in the theory world, you just assume everything is pencil and paper. Everything sits in memory.
14:34 It's you know, it it doesn't matter how you access things. But in real in real storage devices, there is a difference depending how much data you're accessing and in what manner. So random access or non-popular storage is almost always going to be slower than doing sequential access. So what does random access mean?
14:55 It's It's in the name of DRAM, right? I mean, you could like be getting things from completely different locations. So he says you could be getting data from completely different locations. So what does sequential access mean? Nearby is probably still in cache nearby. Well, no, cache is right. It says nearby. Basically, the the data is contiguous. Right?
15:12 And if you if it's kind of hard to wrap your head around this in terms of an SSD because that's all digital. There's no moving parts inside of flash storage. But you think of like an old school spinning disk hard drive, which still exists in a lot of systems today. Right? That's a It's basically a platter of rust spinning around really fast, floating in helium, and then there's this arm like an old vinyl record player that you have to put down and read bits off of the the of the platter as they spin.
15:37 So, if I'm doing sequential access, then I move the arm once, plop it down, and then read as much data as I can uh off off of the device, and then shove it up to the CPU to do processing on it. But, if I'm doing random access, then I'm I'm literally physically moving the arm, jumping out a bunch of different locations. That's a physical movement that that's going to be slow.
15:55 And therefore, the the speed of sequential versus random is going to be orders of magnitude faster because I don't have that physical issues. Now, SSDs, the performance difference is is slightly less because but there is there sequential is still going to be faster. And we can talk about how to parallel operations as well on modern devices.
16:12 That and and that's next week. So, what does this mean? That means that when we design our database system, and again, as we design the data structures and the algorithms, we're going to choose things that are going to maximize the amount of sequential IO that we we can do.
16:28 That means that we may lay out data in such a way to that if we have to spill to disk cuz we run out of DRAM, we can write all that sequentially cuz the sequential writes are certainly going to be faster than random writes. We'll see this later with MySQL.
16:39 What the way MySQL writes uh dirty pages from memory to disk, they'll first write to this side buffer as a sequential write, get that on disk, flush that. That's faster than doing random write. And then in the background, they would then actually go update the physical pages, which may be in in random locations. Right?
16:57 So, they're actually going to write data twice cuz they'll write it out sequentially first. That's fast. Commit that. Tell the outside world your your your data's safe. Then in the background, they'll do the random writes and hide that from you. I mean, there's a bunch of tricks like that that seems crazy.
17:09 Like, why would you want to write something twice? It's because you want to avoid random access. In SSDs, there'll be a bigger difference also in terms of uh reads versus writes. Like reads will be much faster than than writes in SSDs, but that's less less of an issue in not so much an issue in spinning disk hard drives. Right?
17:28 So the way we'll see next class, the way we're going to try to maximize the storage of our data to be sequential or contiguous as much as possible is that when we come to time to allocate memory or sorry, allocate pages on disk, we'll try to allocate large chunks at a time so that through an extent so that the OS kind of try to write them out sequentially.
17:50 So if we say we know we're going to store a bunch of data in in on disk in the future, so rather than allocating 4 kilobytes at a time, maybe we're allocating a megabyte. And yes, there's some unused space, but storage is cheap these days, that's okay. And then that that ensures or tries to increase the likelihood that our data is being stored sequentially.
18:09 We'll do an example with Postgres later on, but doesn't seem doesn't seem they they actually do that though. All right, so the overall design goals we're going to have for our system, not just for the storage level, but also for the rest of the semester, is that we're always going to
18:25 design our system in such that we can assume that anytime we try to go access data, it may not be in memory, it's on disk, and we have to protect ourselves while we go out and get that data from disk. And we have to support databases that are larger than the amount of memory that's available to us on the the single machine. All right, what does that sound like?
18:46 If you've taken the OS class. I'm going to let my data system pretend it has more memory than it actually has. Virtual memory, yes. And then we'll see this later on though, we don't want to rely on the operating system to do this management for us. We don't want to rely on its virtual memory, we're going to do everything ourselves cuz we can always do it better. Right?
19:07 All right, so again, we don't handle databases that exceed the amount of memory from us and give the illusion to the user that we can still support it. Uh we're going to try to since reading writing disk is so expensive, we're going to try to avoid uh anytime we have to read a lot of data, avoid large stalls in our system and let try to let always something do do some useful work for us. Not always possible if everyone is trying to read from disk and the disk is slow, you're blocked.
19:29 But we can design other things to to avoid this. And as I said, random access is always going to be much slower than sequential access, so we'll try to maximize sequential access. That may mean mean we do more work uh in at the CPU level, but it's going to be better for us in the long run. All right, so this is a lot of hand-wavy, a lot of lot of text, a lot of talking.
19:49 Let's just look at what a disk-oriented system looks like. So at the lowest level on disk, there's a database file. Databases, yes, are just files on disk. There's nothing special about them. Uh well, I mean, databases are special, but there's nothing they're not like a special file that the operating system uh knows how to handle or do something special with.
20:11 It just sees a bunch of files. Right? And that's that's the that's the sort of the base the foundation of what we're going to build uh you know, more complicated things on top of it. So our database file is going to have this uh uh some some data at the beginning we'll call it the directory.
20:26 I'll explain what that is in a second. But thing is like it's metadata that tells me what's in my my file. And then we're going to break up the the file into a bunch of pages. I'll explain what that is in a second. It's think of it like a block. Sometimes Sometimes you see things referred to as blocks or pages, right? It's just a way to divide up the data that's in my file at typically fixed offsets so I know how to jump to things more more quickly. And again, in this example here, I'm showing one database file.
20:52 We'll see Postgres in a second. It could be multiple files. Like MySQLite, DuckDB store things as one file. Postgres stores them as multiple files in in much different directories. But for our purposes, we don't care. Then up above in memory, we're going to have this thing called the buffer pool, sometimes called the buffer manager, sometimes called the cache manager, different database systems call different things, but this is basically the memory managed by the database system that we're going to use to bring pages into into, you know, from disk into memory.
21:20 And then there's some other thing on the side we'll cover later uh as we get close to the midterm and after the midterm called the execution engine. Think of this as like the query engine, the thing that executes SQL queries and knows how to read and write data from from the buffer manager.
21:33 So, some query shows up and I want to do something and the execution engine says, "I need to go get page two to execute this query."So, the first thing the database system has to do is says, "Well, I in order to be defined page two, I have to have this directory in."Cuz that's basically again like the lookup table that says where to go find page two and what offset or what file. Again, different database systems do different things, we'll see that in a second.
21:53 So, now once this directory is in my buffer pool, uh you can think of this as like the the TLB, the translation translation lookaside buffer in in at the CPU level, same same idea. But once my directory's in memory, then I can consult that and say, "Where do I find page two?"And say it tells me it's it's in this file at this offset, so I do now a disk read either through the OS or through direct IO to go get the data from the disk file and put it into my buffer pool frame.
22:19 And now once it's in my frame, I hand back the execution engine that or the the thread that requested, the worker that requested this page, I give it a pointer to that page cuz now it's in memory. And we'll talk about how we make sure that things don't get swapped out when we hand off the pointer, but that comes later. Then the execution engine can then interpret whatever's in those bytes uh in that page depending on what it knows to try to access. Is it an index?
22:40 It knows how to access index pages. If it's a table, it knows access table pages. Right? With what these attributes and these types and so forth. All that comes later. And then let's say I want to write some data to this, update it. So, I'll write back to that that that address, the pointer that I got, this page gets updated. At some point I'm the system will say, "Okay, well, it's time to swap this thing out, flush it out."
23:01 So, it's going to write it back to my disk file, make sure that's all durable and safe, and you give back an acknowledgement to the to the application to the execution that the data has been successfully written. So, at a high level, this is what this entire special about is this little little diagram here. And of course, the devil's in the details. How do we do this safely?
23:20 How do we do this efficiently? All that we'll cover as we go along. So, today's lecture and the next two lectures next week will be what's in this file. Right? What are the contents of these pages? What do they look like? What do tuples look like? How can I organize the the the hierarchy of these pages if I have if I need to? Then, uh on starting after that, lecture six will be the buffer manager and also handle disk writes.
23:44 We'll discuss how do we fetch things from from from disk into memory? What do we store in memory? How do we keep it safe in memory? And then, how do we go write it back out if need need be? The writing back out will come after the midterm cuz you have to you have to make sure things are durable and flushed.
23:58 But, we'll we'll we'll talk a little bit about that about it. And then, uh starting at lecture 13, 14, and so forth, we'll then talk about how we actually execute queries. Okay? So, this is the overall road map where we're going uh for the for the next couple lectures up until the midterm. All right.
24:15 So, there's two problems now with database storage. First is, how do we represent data in our files on disk? And then, how do we move those that data back and forth from disk to memory? As I said, today's class uh and next class is on this, and then problem two is when we talk about the buffer manager or memory management in lecture six. Okay?
24:40 So, as I said, the database at its core, a disk-only database system, is essentially a bunch of files, one or more files on disk. Again, SQLite stores everything as a single file. Other systems can store across multiple files.
24:54 And the typically, the database is going to or the database system is going to maintain data in these files in a proprietary format that is specific to that particular database management system. So what I mean by that is you typically can't take like Postgres data files and then start opening them up in MySQL and read them cuz MySQL doesn't know anything about it.
25:14 Right? DuckDB is special cuz DuckDB is trying to be compatible with a bunch of things. You can take a SQLite database file and DuckDB knows how to read that. Uh it might be able to connect to Postgres and other things. Um but typically you know the the the secret sauce of of what the database system is actually going to store data is only known by that database management system.
25:32 Now there's a movement in in the last 10 years over these portable open source file open file formats like Parquet or ORC. You have heard of Apache Arrow, things like that. Right? These are meant to be uh universal file formats that any database system can read and write to. We'll cover that that next week. But most of the systems you can think about, the Oracles, the MySQLs, the Mongos, Postgreses, all going to have their own proprietary formats. And these files are just sitting on what I'll call off-the-shelf file systems.
25:59 EXT4, XFS, or what I don't know what the Windows one is is called these days. Um WinFS, whatever. Like these are just files sitting on the regular file system. There's nothing special from the file system or that person's perspective. There's nothing special about these files except for the database system does with them. Now there was attempts in the 1980s to not use the operating system's built-in file systems.
26:20 So again, not use EXT4 if you're running Windows today. And instead they would ship with their own custom file systems to operate directly on the raw blocks of data in in storage. Um most systems do not do this uh because the overhead of it's so hard to build a database management system, but now you got to build a file system for it? That's super hard to do. You typically see this in the high-end uh enterprise database systems. So Oracle for example will sell you something called uh automatic storage management, ASM.
26:51 And like without ASM, it would look like this. You have a You have the You have your database system, you have operating system, file system, logical volume manager, and then you have a bunch of you know, a bunch of disks.
27:01 With ASM, you get rid of the logical file You get rid of the file system manager of the OS and the logical manager, and then you have this thing running in user space that can do direct IO and manage everything for you down there.
27:15 Beyond performance, there's other management benefits cuz now you have a single interface to the database to manage all your storage versus having to SSH into the box and and and muck around with the file system. Uh again, typically you only see this at the enterprise enterprise level. Most Most systems aren't going to do this. And for our purposes, we're going to ignore that possibility as well.
27:33 So, again, we're just going to assume that we're running on off-the-shelf file system and we're just reading reading running files down there. So, the the the database system's going to have this thing called a storage manager or disk manager uh uh file manager sometimes.
27:46 It has storage engine or whatever you call it another name. Like they're they're all basically the same names with different names of the same thing. And so, the storage manager is mainly responsible for managing these files on disk.
27:59 And it can have components that can be responsible for the movement of data back and forth, meaning they do their own disk scheduling to decide here's how much of requests that I have, how to line them up or batch them up and then and dispatch them. Or in some systems, you just let the OS do it for you. Right? You call it Fread and and let the OS figure out when to schedule your read.
28:21 And as I said, these files are just going to be a bunch of collection of pages. Uh and the database system's going to be is responsible for figuring out what data is being read and written to these pages and when things get
28:34 uh you know, if if I delete things, how to reuse that space, how to do compaction, uh how to expand pages or sorry, expand data across different pages or move it around depending on what the application is trying to do in the data. Most data systems are not going to maintain multiple copies of pages on disk.
28:51 Uh we assume that this is either going to happen at the lower level below us, like the hardware level, like you can buy like things like storage devices, like storage appliances, or you any of you use Amazon S3, they'll they'll replicate that for you and make multiple copies. So, the data system is not going to be responsible for writing out multiple copies for redundancy. All right, we'll do this other ways, but we assume somebody else is going to manage that for us.
29:12 Or it can happen above the storage manager at like a sort of a sort of upper part of the system could do replication. So, one one write request shows up, it can then dispatch that write request to other copies of the data system running somewhere else. But at the lowest level we're not going to be responsible for like for one page write it out four times to have have have duplicates. The MySQL example I said before that's for performance reasons.
29:33 They'll write it out sequentially, right? But then they blow away the sequential file once they've updated the the random file. Right? And for this class we're also going to assume we're talking about tables, uh table data, but you can imagine if you have indexes or other database objects, all these properties still hold as well. Right? But we'll we'll we'll cover this later. All right, so again, storage manager is going to manage a bunch of files that are sitting on disk.
29:58 And then within those files now we're going to break those up into pages. And in almost nearly all systems, a page is going to be a fixed-size block of data within within that file. Now, I can have multiple files that have different page sizes. Uh like again, the enterprise systems let you do that, but for our purposes assume that, you know, a single file has a single page size.
30:21 And just a way to break break up the file into fixed offsets, so you can jump to things very quickly. We'll see how to do that in a second. So, within a page we can obviously we can contain data, like tuples for for for our for our table. Uh there could be metadata about the the data that we're storing.
30:40 Like what was the last timestamp of of when this page was updated or checksum of what the page content should should should look like. We can maintain log records about changes that were made that may or may not apply to the rest of the data. Some indexes allows us to jump to things more quickly within a page. Right?
30:57 The contents of a page also too are going to be uniform, meaning they're only going to be for a specific entity within the database itself. So, I mean you're typically not going to mix in tuples from one table and another table in the same page. Or tuples from an index and a table together in the same page. Some systems will do that, we'll cover that in a second, but like mostly it's going to be all homogeneous.
31:23 Some systems are are required page to be self-contained. And that means that all the information you need to understand what's inside the page has to be stored in the page itself. Let me take a guess why that's a good idea. So, if you read those pages together, you don't have to read other pages or have to understand this page.
31:44 She says if you read the whole page together, you don't have to understand other pages to understand what's inside that page. So, when would you when would that help? I mean, at least saves space for storing the mapping between like if I want to understand page one, I need to go to page three for that metadata. At least we save that storage.
32:07 So, he says if I need to understand what's in page one, I can just stay in page one and get all that information I need and not have to go to page three. So, again, think of an extremes. Think of like my table has a billion tuples and say it's one one tuple per page, I have a billion pages.
32:22 Then would I want to go re-examine every single page over and over again to understand what's inside of it? So, this self-containment thing is good for disaster recovery. All of you are young, all you have have you know new hardware and I'm not running enterprise systems breaks all of the time.
32:43 And so Oracle famously does this because they want to be able to use this for disaster recovery. Meaning if my machine catches on fire and melts half the disk then I can still recover some data because I have enough metadata about what's in the page within the page itself. So most systems don't work this way.
33:02 Most systems will start have a separate pages for the metadata that tells you what the schema is, the catalog about what's what's actually the contents of a table with the attributes and and and the data types. And so if that part of the disk melts, I then can't you know interpret what the others other bits are. But what's that? Yes. So wouldn't creating more copies of metadata pages be more helpful for it to He said wouldn't that create more copies of metadata pages be more helpful? Yes. But it doesn't like what if those catch on fire?
33:30 Right? In the back, yes. So what if the directory information He says what if the the page directory is missing? So again, hopefully none of you have to deal with this, but if it's a true disaster, like the page directory is missing,
33:45 half the disk is melted, you pay for someone to fly out, take the disk, extract whatever data they can off it and like almost like a you know like the when there's ever a plane crash, the federalities show up and try to figure out what actually happened. They literally would sit and look at the bits page by page and try to figure out what's in it. You pay a lot of money for that. Obviously you want to back up as much as possible, but like you know in the old days this was not uncommon. Right?
34:12 Hardware got cheap enough where it's you can you can have enough copies. It's less of an issue. But like that's why they do it. Yes. So it's like I assume like if the metadata remains intact, things like and the actual content there's some disk corrupt it is easier to recover, but what if the metadata itself is corrupted? She says uh the page if the if the metadata is corrupted but the the data itself is fine, what can you do?
34:36 So, you would you'd also have a checksum per page. Some systems will do this. So, you would know whether it's corrupted cuz the checksum won't match. Then you can decide a human have to decide, "Okay, is it the data that's messed up? Is the metadata messed up?"Again, then then you can say, "Okay, well, it's the metadata, but I have another page I know from the same table over here. It should have the same metadata. Let me go use that." But that's that's a manual thing.
34:57 Like the human literally sitting and looking, you know, page by page. I don't That's a job I don't want to want to have, all right? But again, they get paid a lot of money to do to do that, right? All right.
35:08 So, again, but we'll we'll we'll we'll discuss how to do disaster recovery stuff lat- later. Um but again, just be mindful that sometimes you store extra metadata. This seems redundant, but it you're doing it for recovery reasons, right? So, every page is now is going to be given a unique identifier, which we call the page ID.
35:26 Again, the term block might be used, block ID. It's essentially the same thing. And this page ID is going to be a way for us to uniquely identify some page within either the database management system, within a file, within a table or an index, right? Different systems will do different things uh depending on what the layout of of the files are for them.
35:46 Again, SQLite is a single file, so the page ID would just give you an offset within within the file. Whereas in Postgres, the page ID is unique per table. And so, you would go look up the file to say, "What for this table, what file do I want?"And then I know how to jump to an offset based on that page ID.
36:07 And so, this this page ID is going to be useful for us cuz it's going to provide us a way to have an indirection layer to map page IDs to physical locations, and that's going to help us later on. We'll see it in a second because now we can potentially move pages around and not have to update a bunch of other metadata that may be pointing to that page or data structures that are pointing to that page, cuz as long as they have the page ID and there's something recording where to find that page, we don't have to update a bunch of different things. We will see how this really helps us later on when we talk about record IDs.
36:39 So, what's confusing in databases now there's actually three notions of pages in a database system, right? In a computer. So, at the lowest level there's a hardware page, right? And this is going to be what the hardware exposes to you as the the largest size of an atomic write they can actually do. And this is for historical reasons this is always going to be 4 kilobytes. So, what do I mean by atomic writes?
37:01 What does that mean? Yes. Smallest contiguous He says uh smallest contiguous region of memory, or say say block of data that I can continuously write. And what? What does that mean though? Without being interrupted by another read or write. Without He said without being interrupted by another read or write. We're not doing interrupts here. Yes.
37:29 It's either everything is done or nothing is done. Yeah, she said either everything is get written or it's all or nothing. So, if I say to the database system, write this 4 kilobyte block to me, or write this 4 kilobyte block for me,
37:42 and then I give it to the hardware, the hardware says, "Yep, I got it." and gives you back the acknowledgement, if you crash and come back, you should be somewhat guaranteed that that block is going to be there. If I have to write two 4 kilobyte blocks, so total 8 kilobytes broken up into across two blocks, I can't have the hardware guarantee me that it's going to write both blocks exactly or none of them.
37:59 It might write the first one, then crash, and I come back and I only have part half the data I'm looking for. Right? Again, we'll see how to how we how we avoid this problem later on, uh but this is you know, this is something and again, the hardware is going to lie to us, too.
38:18 And the operating system is going to lie to us. We'll see See next class. Uh but this is something that we we have to be mindful when we when we start writing things out. Right? Then there's the OS has a notion of of pages. By default, it's it's 4 KB because that's what uh x86 did in the '80s or something like that.
38:34 Um This is uh in newer versions, you can get uh what are called huge pages. So, this is either 2 MB or 1 GB. Again, we'll cover this uh later on, but for our purposes, assume that the OS is going to keep track of 4 KB pages uh in in in virtual memory.
38:51 And then now within the database system, building on top of an OS page which is built on top of the hardware page, we can have different size pages. And it's going to vary uh per system. Right? So, the uh you know, uh 4 KB is very common in like SQLite.
39:07 Actually, SQLite can go down to 512 bytes. Uh you can change this. Um other systems like RocksDB or WiredTiger, which WiredTiger is the storage manager for MongoDB, right? These guys are going to use 4 KB pages. SQL Server and Postgres are going to use 8 KB pages, and then MySQL can go up to uh by uh by default, it's 16 KB pages. And again, the enterprise servers like DB2, you actually can set the page size the database page size on a per table basis. Right?
39:34 You can make one table be be 64 KB pages, and another table be 4 KB pages. Yes. How do we view the 16 KB uh database page based on 1 GB or 2 MB OS page? Your question is, how do I how do I build a uh if I'm using huge pages, how do I use a 16 KB page if the if the OS is managing uh 2 MB pages?
39:57 You just have multiple database pages within within that. We'll cover huge pages later on. Uh there was a thing called transparent huge pages. The OS tried to be clever and tried to automatically convert your pages into huge pages. That was a disaster. Uh we'll cover that later. Uh
40:14 but forget but just All right, so So, I said it again, sometimes you want four kilobyte sometimes you can have a table have four kilobyte pages in DB2, sometimes you have 64 kilobytes. Why would you want Why would you want to choose one page size versus another page size? Yes.
40:29 I guess if it's better for your operating system of its default page size. He says if it's better for your operating system's default page size. Ignore the OS in this. Yes. It depends on the structure of your data. He says it depends on the structure of the data. What do you mean? If your rows are smaller, maybe it's better to have smaller page sizes.
40:49 He said if your rows are smaller, it's better to have smaller page sizes. Well, if my rows are smaller, then within one page fetch I can bring in more data, more rows, right? Yes. If your reads are supposed to be at a finer granularity, you choose smaller page size. She says if your reads are supposed to be at a finer granularity, you choose smaller page size. Yeah. And then plus also writes.
41:11 So if I have really large database pages and I update one kilobyte but my page size is 64 kilobytes, the database system has to write out that 64 kilobyte page on disk. Right? Again, this this is presuming block-based storage, I can't just write out small small updates. I got to write the whole thing. And because now the system is organizing my page my my files within these larger page sizes, I got to make sure all the entire page makes it out. Cuz I may reorder things, we'll see in a second, depending on how I'm I'm going to implement what's inside the pages.
41:41 So this will be a recurring theme across computer science and especially in databases, there's no free lunch. There's going to be pros and cons to different design choices and it's really going to depend on what our data looks like, which he he sort of talked about. Then also depends on what our workload looks like, which she talked about. If I'm read heavy, I'm doing much of sequential scans on data, then I want really large page sizes.
41:59 Cuz now I'm going to read the entire, you know, I'm going to read all the data within the page, so I want to go one fetch, do a sequential read, do a go bring in a big page into to my buffer pool, and then rip right through it, throw throw and go get the next page. But if I'm a lot of small writes, then maybe I want a smaller page size.
42:16 Cuz then now if I'm if I'm writing a bunch of different random pages that are just, you know, physically in different, you know, different locations, yes, that's going to be random writes, but now I'm not bringing a bunch of useless data that I don't need. We'll see next week an even crazier idea.
42:30 We're all using the term rows to represent data or tuples. What if we don't store it as a row? What if we store it as columns? So now within a page, I just have one column. That's another way to design the system as well.
42:42 Again, we'll cover that next week, but there's there's a lot of different ways to think about how we want to organize organize our databases at the lowest level, and it's going to have trade-offs depending on what we want to do with it. All right, so the the different data systems are going to manage the the the the pages that are in a files in just some different ways.
43:03 The most common one's going to be through heap files, which I'll explain in a second. And it's basically just I have a bunch of pages that are unordered, and tuples can land in in any location. Uh we'll see tree files or index organized uh structures in next week. Um and then historically, sometimes there's things called sequential files or sorted files or ISAMs. This is stuff from like the '70s or '80s. Think of like the pages are sorted in the some value based on the tuple itself. Um and you sort of have that like a indexing data structure on top of that.
43:32 Well, it's it's sort of not it's a let's say it's deprecated. It's like it's a concept or a technique that people don't use anymore. Most systems are going to be using the uh the the heap files. All right?
43:45 So again, I'll also say to you at this point, I've sort of mentioned, oh yeah, you could store things as row store as a column store, but we actually don't need to know anything about what's inside of our pages yet. All right, we just there's some data. We need to be able to a way to to address it. And the heap file is going to be the the most common one. So heap file is just going to be a unordered collection of pages uh that are stored in in random order.
44:08 I mean the the data itself is going to be in some random order. And we'll use a the page ID and some some additional metadata to tell us where to go find the data that we want. So, the only interface or API we need to expose at the the storage manager level, if we're doing heap files, is the ability to create pages within the heap file. Like if the the the the table's getting bigger, I need to append more more pages at the bottom of it.
44:34 Um I need to get a page based on some page ID. You need to write data to a page uh and have it flushed to disk. And then I need to be able to delete a page. And I need to expose some kind of iterator in case I'm doing a special scan where I want to walk through page by page within my my heap file.
44:51 So, to make all of this work, there's some additional metadata we need to do to keep track of what's you know, where the files are located physically on the on on the file system for us. Uh and then what space is available within within it. All right.
45:04 So, if our database is a single file, the metadata we need to maintain is pretty simple to find pages. Right? Cuz we can do simple arithmetic to say, if I want page number two, all my pages are the same size, so I take my page number that I want, multiply it by the page size, and that tells me how to jump to an offset within that file to find the thing that I need. Right? This is what essentially SQLite does, but again, it has some additional metadata to keep track of like what's what each page actually represents.
45:30 Is it a part of the index or some other thing? Things get tricky now if you have multiple files. Right? Cuz now if I want to say get page number 23, I need to know, you know, what file is going to have potentially that that that page. I'm assuming that they're all part of this the same table.
45:49 So, there's going to be a thing called the page directory, and it this will vary per system, but think of it like a hash table that says, for this page number, it's this uh you know, directory at this file location, and here's how to jump into it to get the data you need. Right?
46:02 And then you could then maybe just want metadata within the the header of that file that says, "Here's what the the data looks like below me."So, again, this page directory is a basically essentially a hash table is the way to conceptually think about it. Different database systems are going to do uh different things. But, there'll be one sort of page directory
46:22 uh one entry within within a page directory per database object that says, "Like for for index Y, here's where to go find the the file and jump to offsets and get additional metadata."For this table, here's where to go find other things.
46:35 So, this page directory is like the database of the database cuz it's telling you what files I have, where they're located, and therefore I need to make sure that this this directory is just more pages on disk that this thing gets synced up and written to disk in a safe manner uh along as I'm writing the data pages.
46:55 So, this thing is not updated that often. Right? If if your your database system is if you think you're not do do you know do a bunch of inserts into a table you're not just going to allocate one page at a time, although Postgres will do this. Uh you may want to allocate a gigabyte of data at a time.
47:11 Update the page directory, flush that out to disk, then start doing your writes to your your uh you know, to to your to your table itself. Additional metadata we keep track within the for for about the pages we have. We want to keep track of how much free space we have in per page so that when a when a new insert shows up we're not scanning through sequentially across all the pages to find a free slot to find a free location.
47:33 We just consult this and it's going to tell us where to go find the thing we need. But, you need to make sure that this is actually fail-safe because this free space map, some of it's called, may actually be wrong because we don't need to flush this as like we do with the page directory.
47:46 So, this thing actually might be incorrect for us. And so, if we go jump to a page which we think is empty and it's not we need to be able to give you know, go back and find another the
47:56 We can also keep track of the the pages that are free the free or empty uh so that if we want to do compaction throw them away and get back get back disk space or use it for other things, we can find those quickly. And then some systems will actually keep track on a on a per page basis what the what the page is going to represent.
48:12 Like is it storing data? Is it storing metadata and so forth? So we can consult that to figure out what we're data is actually better jump into when looking at things. So in a really simple example here, so this my page directory is is a the table or database object level. So if I want to do a look up on on for table X page zero, I look in the directory. It tells me where to find the file location that corresponds to table X.
48:35 And then I do that simple arithmetic to jump to a different location. So you can actually see this in uh in Postgres. You can see you can see the internals of Postgres and how it actually lays out of pages and files in in its in its own data directory and what it's actually maintaining for the page directory. So let me switch over.
49:04 Okay, so So that we're going to do that student table we had before. Right? I got three records. So Postgres has a has a extension you can apply called the freeze PG freeze free space. Um and it'll give you
49:26 it thinks it's like a special function that is treated like a table where it'll give you back the space that's available uh for all the pages within a table. So I'm saying for for the the table student take the available space and compute the ratio. So this is saying for block number zero page zero right? It has uh 97% is full. Right?
49:45 Which makes sense because again in Postgres, pages are 8 kilobytes. I only have three tuples. 90 97% of it is full. So, let's insert a bunch of fake data. And this will be a post guest idiom here. Um So, this generate series basically just monotonically increases, you know, some counter.
50:05 Uh and so, I can insert a thousand tuples by invoking the function generate series. And they're all going to they're all going to be the same the same data. So, now uh to double-check that we actually have the data in there. Now, our table has 1,003 tuples. If I go back and now ask post guest how much data I have or how much free space is available on my pages I got a bunch of zeros.
50:32 That's kind of weird, right? And sure, yeah. So, it I had I had one page before. Now, I have seven pages. But, it's unlikely that I stored exactly, you know, have 100% utilization on that last page. Right? That seems kind of odd. So, what's going on there? So, we can actually go look what the files look like for post guest.
50:52 So, they have another function called PG relation file path. And this gives you back now a path on the local file system of where the data for this table is actually being stored. So, now down below I can bump this up. Right?
51:11 So, this is saying that the for the for the the student table, it's in the base directory. So, I go to base. I can show you what it looks like here. So, this is this is post guest data directory. So, there are a bunch of folders here, directories in here.
51:24 I know it may be hard to see, but there's one there's there's a folder one, four, five, and then PG sequel temp so temp data. But, then this one here is 16835 or 385. Let me turn off the turn on the lights. That one is the for for our for our table or sorry, for our database. Is that better?
51:46 Right? And again, when we ran the command to give me the file path, it told us that it was in 16835. So now it says the at the at the within that directory 1688385, it's my data will be in some files called 16653. So we let's go into this.
52:08 And then we can look at the files with 16 653. Right? So here's here's the table. Again, it's just a files on disk. So this thing here 16 653, this is actually the table data. Uh and it's 56 kilobytes. Uh again, multiple of eight.
52:28 And then there's something called the FSM and the VM. VM stands for visibility map. That'll come later when we talk about transactions. We can ignore that. But FSM, that's the free space map. Right? That's how Postgres is going to keep track of what pages have uh free data in it. So now if I go back up here and let's run that same query we did before.
52:49 Right? It's still telling us we have a bunch of zeros and that's because Postgres is not making sure that the free space map is perfectly in sync in memory with with what's on disk. Right? Because it's not How does this It's not super important to have this be exactly perfect. We can write it out at some later point because again, if we get it wrong, then yeah, we create some new pages or we may not be able to reuse pages we uh but that we could have, but eventually that'll all get taken care of we would have used the space. So this is a Postgres idiom, but there's a command called vacuum.
53:22 Think of this as like the garbage collector in Postgres for tables. So if I run that, comes back pretty quickly cuz my table's small. And then now when I when I run my command now you see that again, the first five first six pages are uh are completely full, but this last one here was was only 60% or 40% full.
53:43 Right? So, the vacuum forced the database system to go look at the data and then update the free space map to keep track of where things are. Right? So, now let's do something like delete a bunch of random tuples. Right?
53:59 So, this is saying delete uh tuples that have a that aren't my original three that I started uh based on the student ID and then the random function if you know, flip a coin if it's less than 0.5, delete it. So, we delete about half of them.
54:12 So, again, now if I run the the query to keep track of my free data, in this case here, it decided to update the free space map right away. Right? And now you can see that a bunch of the pages have uh free space. Right?
54:29 So, if I um if I insert 10 more records and now run vacuum and run that query again. You can see that um bring this down a little bit. It I started 10 more tuples. Uh you can't see it on this. Um Nope.
55:03 So, before when I ran the query to say give me all tell me what free space I have for page zero, block number zero, it was at 46% free. Then I said in- inserted the 10 new tuples and then now you see the first block is at 40% full. So, it decided to insert the new tuples in the first page. Right?
55:21 Again, this is an example of the relational model is unordered. I didn't I didn't insert them in the order that uh in my table in the way that they got inserted by the application. It said, "I got some free space. Let me put it there."And that's perfectly fine. So, real quickly, I'm going to show you uh additional metadata that SQL Server will can keep track of for you.
55:40 So, this command here basically hits up the the metadata table uh for a for a table, the student table, and here it tells you I have different page IDs, and then it keeps track of the page types. So, there's the index access map, and then the data page. So, it's keeping track on a per page basis where to find it and what's actually going to be in it. So, this is and Postgres doesn't keep track of these things.
56:01 This is This is a SQL Server thing. And the various data systems are are going to do all different stuff. Okay? Yes. Just curious, does Postgres have like a kind of thing where want to optimize minimize the amount of files used in that case where like 40% utilization.
56:23 So, his question is does does Postgres have a concatenation function? like sort of like in that case there was each file had like roughly 40% utilization. Is there like a I don't see why you would want to do it, but just like out of curiosity, like a way to just squish that into like making each file use more?
56:40 So, is it So, So, his his statement is uh when I when I added the data, we checked the utilization, but the pages had were about 40% full. Is there a way to force Postgres to to use more So, essentially, start moving data around to fill in the space. Yeah, that the vacuum will do that. Uh if you call vacuum full, which we'll cover later on, that literally
57:00 uh will create a new copy of the table by just scanning through the the original copy and then writing them in in in order that they fill it to to minimize the amount of pages you're using. But, that's expensive cuz you take locks on the whole thing and block anybody else from updating it. So, you can't do that. Um Different data systems will will do different things. We'll cover later.
57:19 Yes. When is a vacuum used in an When is a vacuum used in an application? Uh the So, his question is when is a vacuum used in an applic- in application code? You typically, as an application, you would not want to call that yourself. Right?
57:33 Cuz it it it runs on it has various triggers that to when it wants to run on its own. So, for example, if you if you if you update, I think, 10% of the tuples in the table, then it'll run. Right?
57:45 Or you can set it to be like it'll run every night or something like that, right? There's ways that this is a server at the administrator level. Yeah. Yes. Why are we storing both table to file mapping and index to file Question is, why are we storing the the table to file mapping and index file mapping?
58:02 Yeah, and index Index So, uh uh I mean, so it's in this example here, there's some the directory is saying, "If you want to know about table X or other database objects, like an index or other things, here's where to go find it."Right? Cuz and then cuz otherwise, you'd have to know like, "I'm trying to access the index."And you store it directly for indexes and separate pages and separate tables.
58:23 There's no reason not to reuse them. That's all it That's all it means. Yes. For the index, is it for every His question is, for the indexes, is it for every value on the index? Again, at this point, we don't know anything about values. We don't know anything inside these pages.
58:40 I'm just saying like if if if I'm looking up for page 123 on index Y, I don't know I you know, I'm not saying what I'm looking for inside the index. I'm saying where to go find the page for it. It's at the lowest level. The page directory will tell you where to go find that page.
58:55 Then, once you land inside that page, then you interpret the page to say, "Okay, what data structure am I looking at? Is it B+ tree, a hash table, whatever? How to go then find the value within that index?"At this point, we don't know anything about what's inside these pages.
59:09 We don't care. Yes. Where exactly is the free space map stored? Is it like in memory? His His question is, where's the free space memory free space map stored? Is it on disk or is it in memory? It's in both. Some Some data systems will store the free space map as part of the page directory metadata.
59:27 Right? Some of them, like in the case of Postgres, will store it a separate file that then's mapped in into memory. I brought it into memory. I don't I don't Map to sounds like it's using Mmap. We're not doing that. Okay.
59:44 So, um All right. So, again, now we know what the It's roughly how we're going to organize files. Now we got to talk about how we're going to organize pages. Um And today I said the within a page there's going to be a header that's going to tell us information about the page. We talked about before about the the case of Oracle where they they're storing all the the schema information in the page itself in the header.
1:00:08 Most systems don't do that, but there's other things we want to store as well, like what the size of the page is, a checksum. Often times you want to know what what the version of the database system that created that page is. So, like if you upgrade versions of your database system, it's it's going to scan through all your data and go figure out whether the the format of the page is an older version and try to change it for you.
1:00:26 Let's see what I can show you. Transaction visibility information, we'll cover that later. Some systems will compress data and encode it in a different way. We'll cover that next week. Metadata to say like within this page it's still tested in this manner. Schema information we talked about before and then sometimes there's additional metadata, like a summary of the data that's inside of a sketch.
1:00:46 Like the save you can keep track of the the max the min max value for the data I forget you So, if my page is really big, maybe I I just read the header and I'm looking for values within a range and I know if the min max value is is outside the range I'm looking for, then I just skip reading the rest of the data. We'll see that more in the column stores next week.
1:01:09 But again, there's always going to be some header within the page that's going to tell us what's in the page. So, now the next question is how are we going to organize our data within these pages at sort of a um or basically how we're going to lay out the tuples themselves.
1:01:29 Right? For now we're going to we're we're ignoring indexes. We'll cover that later. But like if we have a bunch of tuples, how are we going to put them in in in these pages and what do we actually want to store with them? So I'm starting to talk about column stores, but that we'll cover next week.
1:01:44 But just assume now we're just storing all the data contiguously for a single single record as a row and then when that tuple's done, then we have the next record. And we're going to assume also too now for now, but we'll fix that next week that all the attributes for a single tuple are going to fit in a single page. Right?
1:02:03 So there's basically Yeah, you also need to be talking to hear you over the There's two points that we're going to cover now. That's fine. That's fine. And then we're going to have two different ways of storing our data. So we lost the signal we're talking next week.
1:02:15 Yeah, you can you can Can you hear me okay? We're basically I'm going to store Okay. Let's go. tuples, but I'm going to store redundant of them as they get updated in in a as if it was a like a log.
1:02:27 And then index organized storage is what MySQL and SQLite do and other systems do where I think of the the the the table's organized as a tree as a data as a data structure and then the the leaves of the of the tree will be the actual data itself. So it'll be mixed with like inner nodes and leaf nodes within it as well.
1:02:41 But again, we'll we'll cover that next week. So today I just want to focus on uh tuple oriented storage and then these guys we'll pick up next class. All right. So say we have a page. We want to start putting tuples in it. So how do we how do we want to do this?
1:03:01 So a straw man approach, meaning it's a bad idea, would just be in our header we keep track of the number of tuples that we have and as new tuples get inserted into the database, we just find the you know, just do the math and jump to the to to the the location of where there's free free space in the page and we just start writing it out. Until we run out of space, and then we move on to the next page.
1:03:23 So, this is clearly a bad idea because well, what happens if I delete a tuple? If it's the same size, they're all fixed length, then that's not a big deal cuz I just insert it in the next free slot. But now, if my data is going to be variable length, meaning every tuple is not going to be the same size, which is very common.
1:03:37 I think of your email addresses, those are always different sizes. Your Android ID is always different size. How am I going to make this all work now in my in my in my page? So, this approach is actually what log-structured databases are going to do, but they'll do it they'll still handle variable-size tuples. We'll cover that next time. But for our purposes here, this is actually a bad idea because this it's going to be tricky for us to always be able to find free space to store the things we want to store.
1:04:05 And now too, if you start moving things around in our page, like maybe you want to put four after three, now we got to go update everything that may be pointing to tuple four, like an index, to say, "Hey, your your location got changed."So, a better approach is what is called slotted pages.
1:04:23 Now, what I'm going to describe here is a high-level what a slotted page looks like. This is what pretty much every row-oriented database system does. May not be exactly as I'm describing here, like the details may may slightly different, but at a high level, they're going to have some slot array, and they're going to move things around, and and it's going to work basically the same way. What they store in the header might be slightly different.
1:04:41 So, the way a slotted page layout's going to work is that at the beginning of our page, we're going to have the slot array. Right? Just you know, fixed length offsets to different to to locations in the in our page. And then now, at the bottom of the of the the page, it'll be all the fixed-length and variable-length tuple data.
1:05:03 And the idea here is that the as we add new tuples, we're going to append them to the the end of the page, so it's going to grow from the from the end to the beginning, and then the slot array is going to grow from the beginning to the end. And at some point they'll meet in the middle cuz they run out of space and our page is full.
1:05:19 So, this slot array is just getting these these offsets in inside the page to say if you want, you know, the the tuple at position one, jump to this offset and here's where it is. And again, the slot array grow grows this way, the the data grows this way. And at some point you run out of space.
1:05:38 So, now, if I delete data in this approach, so if I say delete tuple three, then all I need to do is just mark it as being deleted in the slot array with the header to say this thing is has been emptied and I'm done. You're shaking your head, no.
1:05:56 Why? You're shaking your head, no. So, you you you made this that was like as if it's a bad idea. Okay, okay. So, in this case here, yeah, I could I could delete tuple three and I don't have to update anything. Right?
1:06:11 I could just leave the data where it is, that's fine. Some systems actually will decide, okay, well, and now I got this free space here, so let me compact things. So, they'll say take move tuple four back to where three was, compact it, free up space, and then now I just update its slot array offset to point to its new location.
1:06:31 Is that a good idea or a bad idea? He says bad idea. Why? Like when you want to insert new data into it, Yes. probably you got no enough space in those empty slots and stuff. He says if if you want to insert a new tuple into it, I have a lot of free space and I'm okay, it's fine.
1:06:53 Yeah, but what if what if I have a small tuple that could fit in there? Yeah, but you always have like wasted spaces or something. You always have wasted space, but I certainly would have lot less wasted space if I can compact it this way. In the back, yes.
1:07:08 If we have a lot of small spaces, then we have to like shift all of the tuples into like one area He says if you have a lot of small tuples, I have to shift things into different areas and it would be very wasteful. Is that bad?
1:07:25 So the answer here it depends. Right? All right. Not to cop out. Right. So in this case here uh And you're also you're thinking about it in terms of of of you're ignoring disk. Getting things from disk is super expensive. Once it's in memory, it's a essentially free or cheap to work on. So if I do this, if I compact things to free up space, that's sitting in memory, that's fast. That's that's not a big deal.
1:07:52 Versus like having to go fetch another page and bring that into memory because I don't have free space in this thing. Right? But though, as I said before, you want to have try to have most of the data you need sitting in memory. So therefore uh when I'm doing this shuffling around, I have to hold the latch on the page.
1:08:10 Latch is the lock. We'll cover that in a second. All right. Like I'm holding the latch on this page for a longer time. So other people may be trying to access this page but they can't get to it because I'm moving things around. So they get blocked. So some systems will actually move these things around.
1:08:22 SQL Server does this thing. Oracle does this. Postgres does not. And there's there's pros and cons to all these approaches. Right? All right. We're well over time. Um so let me break here. Uh we'll come back to record IDs cuz I don't I want to switch over to to the Neon talk.
1:08:40 Um but this slot of page architecture is is is fundamentally I'm pretty much how every row store system is actually going to operate on. Okay? All right. So let's see if uh we can get to Hekky.
2. Jump to
1:08:55 Okay. So again, this is Hekky. He's awesome. Uh you're a Postgres committer, right? I am. Uh yeah. Well, yeah, let me get started. So, I'm I I do have a slide on that actually. So, yes, I am a Postgres committer. I've been hacking on Postgres for for many, many years. There's a picture of me like 15 years younger wearing a Postgres sweater. Um and now I'm a co-founder of Neon, but I worked for many different Postgres companies around Postgres for a long time.
1:09:20 So, I was eavesdropping listening to you speak for the last 10 minutes and it was a lot of familiar stuff. It's funny to hear that. I love with the with the tuple format and all that. Um but yeah, so what is Neon? We provide Postgres as a cloudless uh serverless cloud service and it's developer-friendly. Kind of the unique features we have is is branching and auto-scaling. But really what is probably more interesting for you guys is the architecture.
1:09:45 Uh so, all of those things are kind of enabled by the architecture, which is separating compute where how we separate compute and storage. Uh I'm going to dive right into that. So, separation of compute and storage. First of all, compute in this case means Postgres. So, we run Postgres uh in the cloud for you and that is the compute part. Like that's the part that our users actually interact with. Like they connect to Postgres, they run their queries there.
1:10:10 Uh same as any other Postgres instance. The storage part is is something that we wrote from scratch uh in Rust. Like it's a it's a whole new system. And uh it it's it's designed to work with with Postgres and it knows knows a little bit about Postgres's like page format and and uh the write-ahead log and so forth. But the way it works is that whenever Postgres modifies a page uh normally, like it writes it to the write-ahead log, and it also keeps it in the buffer cache as a dirty page and so forth.
1:10:40 But what we do, we intercept the WAL stream. So, whenever Postgres makes any modifications, they go to the write-ahead log and we stream the write-ahead log to to our storage system. And the storage system consists of a few parts. I won't go into too much too much detail, but kind of the page servers is where we have most of the code. Uh the But the safekeepers is the first thing that in deserves the wall.
1:11:02 And there is a consensus algorithm going on there based on Paxos where the write-ahead log gets streamed to the safekeepers and the safekeepers kind of make sure that you don't lose the recent transactions. So, at least three of the safekeepers have to receive the wall and then we acknowledge the commit to Postgres as as committed.
1:11:22 So, this is kind of reusing all the same machinery that Postgres normally has for synchronous replication or safekeepers as storage system kind of looks like a synchronous replica from Postgres' point of view up to this point. But then there's a lot of a lot of stuff that happens in the page server side to to process the write-ahead log. And what is kind of unique about this storage system is that we we keep all of the logs, like we keep all of the history of your database,
1:11:47 but we process it in into a format into what looks a little bit like a log-structured merge tree where we can quickly access any of the pages. Uh And that becomes important when when you when you're implementing stuff like branching.
1:12:02 Uh time travel query is another very cool feature that Postgres can do, which is much more harder with with vanilla Postgres. The This is the way this kind of looks like from Postgres' point of view is that we we plug in at a pretty low level, so pretty close to where Postgres normally like writes an 8 kilobyte page reads an 8 kilobyte page from disk. We kind of intercept that call and we do this network request to the page server instead.
1:12:27 And then the page server will reconstruct that page using the write-ahead log it has and and then it all page images it has. But that's kind of the gist of it. So, the page server reconstructs the page and sends it back to Postgres.
1:12:39 And all of these requests also contain like an LSN number, so the the request is always get page number 123 at this specific LSN. And that's what allows you to do the time travel query because you can just ask for an older page version, or any page version you want by specifying the right LSN.
1:12:57 Now, one interesting thing about this architecture is that cuz the page servers handle all of the reconstruction of these pages, uh when Postgres normally writes a page to disk, like evicts a page from the buffer cache, uh that operation is just a no-op on Neon. So, we just throw the page away, uh because the storage system can always reconstruct it from the wall it has.
1:13:15 So, you you don't need to write it back. And that means that there is no checkpointing in Neon. Like, you don't need to do checkpoints. It's done continuously by the uh the storage system. Um we we still do go through the motions of a checkpoint. Like, the code is there, but it doesn't actually do much because it just throws away the pages that you would normally write to disk. So, the storage system is a single writer node uh single writer system.
1:13:38 We don't try to do like distributed queries or distributed uh transactions. Turns out those things are hard. I'm sure you you will have a courses on all those things as well, but there's always tradeoffs and like either with performance or consistency or whatnot, and it tends to be difficult. And it's especially hard to retrofit like a distributed system on top of an existing database like Postgres.
1:14:04 Uh but in practice, we can we can support multiple readers, so you can scale out your reads, and that means that you kind of free up the capacity for the rights in a single node. And you can actually process quite a lot of transactions uh in a single node these days. Like, computers keep getting faster. Uh the storage system is multitenant, written in Rust, uh and it allows you to do these things I mentioned.
1:14:26 And it's open source if you want to take a look. But actually, one and there is like an earlier presentation of that that I gave at and this uh database series, so you might want to look at that for more details on the storage system. But what I want to also touch a little bit is how we actually make Postgres serverless. Um well, one part of it that is that separation of computer and storage.
1:14:46 So, that allows us to spin up Postgres very fast. Like you don't need to do wall recovery when you start Postgres on Neon because it can just connect to the page servers and start asking for the pages at whatever point you want without having to kind of sequentially replay the logs. Um that allows us to kind of spin up Postgres very quickly.
1:15:06 Then the other important part is a proxy, which is pretty straightforward. There's just a proxy that intercepts the connections, but then it goes through the all of this stuff to orchestrate and start up the Postgres servers if it's not already running and so forth. Um and finally we put Postgres on in a VMs in Kubernetes.
1:15:22 And there's a lot of orchestration involved in in how how to actually manage all that. Uh one part of this is auto scaling. So, VMs can be you know, scale up and down. We run a lot of VMs on a single big host. Um but there's some interesting questions on when do you want to off scale and down scale?
1:15:39 Like CPU is kind of straightforward. Like you know, if you need more CPU resources, you you can have more and you can kind of never run out of CPU. Things will just If If you don't have enough CPU resources, then things will just go slower, but nothing everything still works. Uh disk is a little harder.
1:15:55 Like if your query needs a lot of disk, you have to provide that disk or otherwise it fails. So, the the question there is to just make sure you have enough basically, but memory is hard. We haven't fully solved this problem yet either, but these are the kind of problems we're dealing with at the moment and we're working working really hard. But I kind of want to plant this idea to you guys. Uh So, when do you actually want to add more memory to a a database server?
1:16:22 Well, kind of trivial case is if you're If you're about to run out of memory, then you might have a more then you probably want to have more memory so you don't run out. Although there's exceptions there. Like what if you have a runaway query that is just going to consume infinite amounts of memory if you let it run? Like do you still want to just keep adding more or you know, when do you actually want to cut that off.
1:16:41 Um But that's that's pretty straightforward. Kind of the next level is that you might want to add more more memory to a system so that you can have a bigger cache. Like Postgres can run pretty big queries with very little memory. It will just be slow. Uh but all of the core parts can like work with little memory if you only have a little memory available.
1:17:02 Like sorting for example, you start with a quick sort and then you move on to on-disk sorting. Or you know, you can change to choose the size of the cache the way you want. But when would you want to add more memory? Like if if you would add more memory to your system, maybe your database fits in RAM and now it's really fast cuz it's an in-memory database. But you also don't want to just always do that because there's no limit to how much you might need.
1:17:28 So that's kind of an unsolved problem but it and it also depends on the cost. Like how much are you willing to pay for those things? Kind of the third level is like what if you added more memory and now you could do a different completely different query plan and that affects the optimizer too. Like if you knew that you had more memory, you might have chosen a hash join instead of a merge join or something.
1:17:49 And that kind of changes the game altogether. Like you can't just look at what the query is doing when it's executing. You actually have to predict what it would do if you had more memory. We haven't solved that problem but it's an interesting research problem that we are hopefully try to do something this autumn. We love Postgres.
1:18:07 So I'm a Postgres hacker myself. Um So that's kind of a given with the company. But there's a lot of business reasons too. Like we we haven't changed the planner, executor. All of the extensions work. Like there's a big ecosystem of Postgres tools out there. There's also a lot of like blog posts on how to do things with Postgres and like tuning advice, all of that.
1:18:26 And we try to make sure that all of those things all of those little random snippets of information that you find on the internet would also apply to Neon because that makes it easy for people to work with it and cuz it's the kind of the
1:18:41 it's back and future compatible with upstream Postgres which makes it a lot easier to you know if you already have that experience. One interesting thing is that I want to point out is that Postgres still handles MVCC the way it always does in Neon even though our storage system
1:18:56 like keeps all of the history so we could actually go and do time travel query that way but we don't use that for the MVCC part. Postgres still handles that the same way with you know different row versions on pages as always. That was kind of all I had prepared.
1:19:10 I hope you have a lot of good questions for me and hopefully I will also have some answers. All right, we have time for like one or two questions. Raise your hand and I'll repeat it to him. Yes. What is the advantages of Neon over PlanetScale besides they're different from Postgres and MySQL? So his question is what is the difference between Neon and PlanetScale besides besides other than I uh other than just being MySQL versus Postgres.
1:19:41 I don't I don't know PlanetScale very well. I don't think they do the kind of storage system we have where where you can do branches and like they I think they do that differently but to be honest I don't have any look at the details of how exactly they do it. I know you know nothing. Yeah.
1:19:55 Can I answer it? Sure. Yeah, go ahead. So PlanetScale is doing doing the distribution at the front level that the front of the system, right? Meaning it's it's based on this thing called Vitess that came out of YouTube. It's how they scale MySQL at YouTube. So query shows up at and then at the front line they say, "Okay, where do I need to go?" and then move data around.
1:20:16 In case of Neon they're doing distribution at the lower level meaning like they you hit Postgres up, they fake Postgres out thinking it's talking to it's regular file system but instead it's talking to this Neon storage thing that he built and then they do all this distribution below that. So it's like one comes from the top, one comes from the bottom.
1:20:34 Thank you. Other questions? So, I So, Hikki, right now you're also in Europe, right? Yes, Finland. He's in Finland, so we appreciate him being I guess it's what, 9:00 9:00 p.m. Um and then so there's uh one of our best former students, Chi Zhang, is actually a full-time employee at uh Neon right now, and then one of our best undergrads is doing internship with uh Yuchen Liu as well and you're taking them to Portugal next week?
1:21:02 Yeah, we're going to a full offsite meeting next week. Um okay, so let's thank Hikki real quickly. Thank you. And actually, uh one quick thing, if you interview at Neon, do not tell them you're not as good as Chi. Okay? You may not know who Chi is, but like I've had two different companies tell me that students show up and tell me they're not as good as one of our former students. Do not say that, okay?
1:21:27 You're all awesome, okay? All right. All right, Hikki, thank you so much. Uh all right, guys, have a good weekend and then see you uh on Monday next week, okay? Mhm, I need something refreshing when I get finished manifesting. Too cold to hold blow like Smith & Wesson. One chord in my thoughts, hip hop related. Write a rhyme in my pants intoxicated. Lyrics are quicker with a sip of malt liquor. Since I'm a city slicker, play waves I pick up.
1:21:53 Rhymes I create rotate at a rate too quick to duplicate. Feel the breeze as I skate. Money's at Fahrenheit when I hold a wheel tight. When I'm in flight, then we ignite. Blood starts to boil. I heat up the party for you. Let a girl rub me and my mic down with oil. Records still turn with third degree burns for one man. I heat up your brain, give it a suntan. So, just cool let the temperature rise.
1:22:17 Then cool it off with sane eyes.