Database Storage (Part I)

 We want to understand what a database looks like at a logical level and how to write queries to read/write data from it.  

The outline would be relational databases, and going through different parts of a database system, one by one. 

The database is assuming the primary location of the database is on disk. This means you may want to access data that's not in memory and we have to go on a disk and get it. To understand this a bit further, you need to differ between volatile and non-volatile storage.

Here is the storage hierarchy of computer. The top is faster, smaller and more expensive like Registers, and Caches and at the bottom are the Spinning disk hard drives, and network storage. At the bottom, they are much smaller and cheaper. 

Everything on the top gets wiped when you pull the plug. There's other aspects that are going to affect how we're going ro design software. Byte-addressable address can get exact 64 bits. Non-volatile storage you can't get exactly the bits, you need to get the page that you want, we have to get everything that's along with the page. 

Another aspect is that these systems usually have faster things. Another aspect is these systems have faster sequential access because I can read the sequential blocks more efficiently than simply reading random locations. Let's just call anything in DRAM memory and anything below the line is the disk, but we don't really care which one of these it is, in most of these. Network storage is like S3 at Amazon. 

There is a class of storage now called Non-volatile memory, or Intel-Optane Memory. It's like DRAM and is byte-addressable, but it's like an SSD where you still get the data. Eventually, we'll have to rewrite the class to take this into account. 

L1 Cache has 0.5ns time, L2 is 7ns, then DRAM, SSD, HDD, Network Storage, and Tape Archives. We want to minimize the impact of reading data on the disk. We want to provide the illusion to the application that we have enough memory to store the database. We want to be careful on any single time we read from the disk, and we're going to minimize that impact.

Disk Oriented DBMS can be represented as different blocks and pages. We then have a buffer pool in memory, which is a higher level layer, which is a query engine saying ("how to read page 2) and then we get the pointers to memory, and get to memory, then after this we interpret this pointer, and we don't really care that way.  

We're trying to make more memory appear that there is. 

Why not use the OS? One can use mmap (memory mapping) to store the contents of a file into address space.  So after mapping, I can read and write to these memory locations. So we're giving up control of data and memory back and forth. We let the operating system manage this for us. On a high level, the application wants to read page 1, and it looks at the virtual memory, we fetch the disk, back it into physical memory and now point the page into the memory location. 

I might have to read something that is not in memory. How do we mitigate the stalls inside of the disk? The operating system has no idea on the semantics on what a query is, what data needs to be read. We're giving up knowledge over to the OS that's blind and doesn't know anything. 

There's syscalls that can mitigate these problems, but becomes problematic. The OS sees that it needs to go out and write the data. We use madvise to tell how to read pages, prevent pages from getting paged out, how to flush memory, among other processes. 

madvise is Tell the OS to read certain pages. mlock tells the os that memory cannot be paged out and msync tells the OS to flush memory out of the disk. There's not very many solutions to this. mmap() gives up control and the data system can always do better than what the operating system tries to figure out. mmap() had a huge bottleneck and raise a load of money, and then bought a non-mmap() storing engine. mmap is unattainable. 

The OS is NOT your friend, database systems wants to control things and can do a better job at it. You need it to survive, but ideally, you don't want to talk to it.

2 problems is how do we represent data on files on disk, and how do we manage memory and move data back-and-forth from the disk? We'll talk about file storage, page layout, and tuple layout here. 

The database is just a bunch of files on disk. SQLite only scores 1 files and most other directories store databases across multiple files. The OS doesn't know anything about the content in these files, there's a bunch of data which is not special. You can't take a SQLite file and think MySQL can read it, data is specialized to the software. 

Databases are typically stores on top of the software that the OS provides. In the 1980s people tried to use custom filesystems and raw storage, managing themselves. Most newer systems don't do this, but Oracle still does. Doing this is harder and less portable.

The storage manager is responsible for maintaining a database's files on disks. We could do reads and writes and have the OS schedule things. Sometimes we allow a database system to do its own disk scheduling, and have different blocks to perform a single write request. Most systems don't do this, and it's typically for the high-end projects. 

A statement is "if I have one filename and inode, or multiple files and multiple inode, and a bunch of metadata", it's a kilobyte of metadata, so more metadata is better, since it doesn't make a difference for really large scales. We'll organize files as a collection of pages, tracking data read/written to the pages. A page is just a fixed-size block or chunk of data, and a page can contain anything, tuples, data, metadata, indexes, log records, really anything. 

Some database systems might have to store the contents within a page itself. I can have the metadata of the table stored in one page and the tuples in another page. However, if I lose the page, I don't know how to interpret the contents of the pages, so now the metadata needs to be in the page itself. The overhead might seem crazy, but they do it for disaster recovery, and all the metadata in the page is stored within itself. 

We're not going to mix or try to mix multiple pages with each other. Each page has an internal system, a page ID. Then there's and indirection layer that maps a page id to some location in a file. Each page is given a unique identifier. 

At the lowers level, the Hardware page is the access level/api that you get, which is 4KB, then afterwards you have an operating systems (OS) page, and a database page (512B - 16KB). The database page is what we care about. 4KB is like SQLite and 16KB is like MySQL, but we care about the hardware page is the lowest level that we do atomic writes to the storage device.

The hardware can only guarantee that writing and flushing to the disk will be atomic. Like when I say I need to write 16KB then it might crash and now we have a torn write, since the hardware can only guarantee 4 Kilobytes of a time. 

Now, let's represent the page storage architecture. The most common one is Heap File Organization. A heap file is an unordered collection of pages where the tuples, or the data, can be stored in random order. The API we need is to be able to read, write, and access pages at a time, as well as being able to iterate through all of the pages at the same time. We need to keep track of metadata to find out what pages exists and which ones have free space.

We can represent pages with linked lists and page directories. We're trying to figure out within the file, where pages exists and whether they have data or not. In the header of the linked list, we just have 2 pointers, where there are free pages, and now just points to the nth page or the data that points to a particular page of a linked list. The heap file is unordered because the data that we are storing does not need to be ordered when sent. 

Now we'll do a scan until I find pages that have scans, so it's basically a 2-direction linked list. I can either do binary search to find the page I want, or get the linked list. The linked list is a logical thing that is built on top of the heap file. The main takeaway of this, is this is a BAD IDEA! 

We can also maintain additional metadata and the free space that is available to me on a particular pag. The pages are just ordered sequentially and there will be a mapping to where the pages are located, and this is sequential and can be more reliable. Each page has the same size. 

Some database systems use larger pages, because there's going to be trade-offs. Internally, we're mapping pages to some location in memory, but the larger amount of data I can represent, the amount of memory needed goes down as a result. If I can write out contiguously, when I do a read, I can just read that sequentially, and get potential data, but there's inefficiencies, because it makes writes more expensive. Commercial systems, you can tune different ways in regards to writing to the database system. We can't guarantee the page directory is self-contained, or complete. We can also put checksums in pages to protect data after a crash, to know if I have an error or not. 

Every page has a header of metadata, and data. The header has page size, checksum, transaction visibility, and compression information, and some systems, such as oracle, require pages to be self-contained. 

Within a page, we can represent data in 2 different ways. We can do a tuple-oriented approach, or we can do a log structure approach. Now let's talk about what it looks like looking inside of the page. We can see how many tuples are in the page. In the page, we can just insert tuples one after the other. We might update the content. This is a bad idea, because if we delete a tuple, we have external fragmentation, or we will have to move everything in the tuple back up. I either need to maintain metadata to see where to write data, or sequentially scan of every single tuple.

Now instead people will use slotted pages, at a high level this is what everyone does. We'll always have the header storing data about checksums/ acces. The top is the slot array, and the tuples. The slot array is a mapping layer to a slot from some offset in the page that is the starting area of a particular tuple, and now we can move the tuples anywhere we want. The page is full if the slot array and the tuple already extends, and this is how to do data length tuple, organizing defragmentation is complex. 

We're trying to store tuples inside these pages, and ONLY pointers for tuples inside of these pages. Don't do this for a video file, since there's some extra metadata and pointers, "Here's the data that you're actually looking for." We'll break that assumption next class, but for our purposes, it's fine. We just have to change the slot-array pointers as a result. Indirection layers avoid having to have all updates in the system. 

We identify tuples through record ids, or tuple ids, a unique identifier of the logical address of a tuple, a blend of logical and physical. Other parts can have the page id and a slot number, so I go to the page directory, get to the page, and then we see the  slot array, and tells me where in that page that I can find the data that I want. 

Index ex: Page 123 Offset Slot 1. 

The index doesn't have to be updated even if we move the page around. If there's tuple that is inserted and there's tuple 1,3 then we insert to slot 4, since postGres is at the end which is a vacuum, or the garbage collector. Different database systems have different ways to insert specific tuples. Other languages compact the tuple into the free space. Internal columns using an asterisk doesn't do anything but for you need to specify the column. 

POSTGRES we can say where and access a tuple exactly based on storage location. 

SELECT r.ctid, r.* FROM r WHERE ctid = '(0,1)'; but this shoujld ONLY be used to allow administrators to know what's going on. You can't name a table ctid, and there's a bunch of reserved names in SQL. 

The next topic is Tuple Layouts, and a tuple is just a sequence of bytes. It's the job of the DBMS to interpret those bytes into attribute types and values. 

We'll have a header and the actual metadata and these are actually tuples. We don't need to store the metadata of a tuple within the tuple itself, we store this in a higher-level metadata information. You have to do this in MongoDB because every single tuple can be different. 

Inside the tuple data itself you typically store them in the order that you created the table. Here's how: 

You should not store data from different tables inside of the same page. You don't want to do this because you don't want a bunch of extra metadata when you want things to be self=contained. People cry when you try to teach them, and nobody does this in reality. You can denomalize and store them in the same page, and it potentially reduces amount of I/O for common workload patterns, and it can make updates more expensive. You might reference the foo table as follows:

CREATE TABLE bar (

c INT PRIMARY KEY,

a INT 

    REFERENCES foo(a),

);

Instead, maybe what I want to do is to embed the bar tuple directly inside the foo tuple, just have the columns that are unique to the other table. This is called denormalization, in other words, prejoining.

This the only time systems try to store data in the same tuple, and this is a very old idea. When you can define JSON document, you can prejoin attributes within the JSON document itself. 

The database is organized in pages, and there are different ways to track and store pages, as well as different ways to store tuples.