Storage

Volatile Devices:

Volatile means that if you pull the power from the machine, then the data is lost.
Volatile storage supports fast random access with byte-addressable locations. This means that the program can jump to any byte address and get the data that is there.
For our purposes, we will always refer to this storage class as “memory.”

Non-Volatile Devices

Non-volatile means that the storage device does not require continuous power in order for the device to retain the bits that it is storing.
It is also block/page addressable. This means that in order to read a value at a particular offset, the program first has to load the 4 KB page into memory that holds the value the program wants to read.
Non-volatile storage is traditionally better at sequential access (reading multiple contiguous chunks of data at the same time).
We will refer to this as “disk.” We will not make a (major) distinction between solid-state storage (SSD) and spinning hard drives (HDD)

In this project, we will refer to DRAM storage as ”memory” and anything below that as ”disk”.

Disk-Oriented DBMS Overview

The database is all on disk, and the data in database files is organized into pages, with the first page being the directory page. To operate on the data, the DBMS needs to bring the data into memory. It does this by having a buffer pool that manages the data movement back and forth between disk and memory.

The DBMS also has an execution engine that will execute queries. The execution engine will ask the buffer pool for a specific page, and the buffer pool will take care of bringing that page into memory and giving the execution engine a pointer to that page in memory. The buffer pool manager will ensure that the page is there while the execution engine operates on that part of memory.

File Storage

In its most basic form, a DBMS stores a database as files on disk. Some may use a file hierarchy, others may use a single file (e.g., SQLite).

The OS does not know anything about the contents of these files. Only the DBMS knows how to decipher their contents, since it is encoded in a way specific to the DBMS.

The DBMS’s storage manager is responsible for managing a database’s files. It represents the files as a collection of pages. It also keeps track of what data has been read and written to pages as well how much free space there is in these pages.

Database pages

The DBMS organizes the database across one or more files in fixed-size blocks of data called pages. Pages can contain different kinds of data (tuples, indexes, etc). Most systems will not mix these types within pages. Some systems will require that pages are self-contained, meaning that all the information needed to read each page is on the page itself.

There are three concepts of pages in DBMS:

Hardware page (usually 4 KB).
OS page (4 KB).
Database page (1-16 KB)

DBMSs that specialize in read-only workloads have larger page sizes

The storage device guarantees an atomic write of the size of the hardware page. If the hardware page is 4 KB and the system tries to write 4 KB to the disk, either all 4 KB will be written, or none of it will. This means that if our database page is larger than our hardware page, the DBMS will have to take extra measures to ensure that the data gets written out safely since the program can get partway through writing a database page to disk when the system crashes.

Database Heap

here are a couple of ways to find the location of the page a DBMS wants on the disk, and heap file organization is one of those ways. A heap file is an unordered collection of pages where tuples are stored in random order.

The DBMS can locate a page on disk given a page id by using a linked list of pages or a page directory.

Linked List: Header page holds pointers to a list of free pages and a list of data pages. However, if the DBMS is looking for a specific page, it has to do a sequential scan on the data page list until it finds the page it is looking for.
Page Directory: DBMS maintains special pages, called page directory, to track locations of data pages, the amount of free space on each page, a list of free/empty pages and the page type. These special pages have one entry for each database object

Page layout

Every page includes a header that records meta-data about the page’s contents:

Page size.
Checksum
DBMS version
Transaction visibility
Self-containment. (Some systems like Oracle require this.)

There are two main approaches to laying out data in pages: (1) slotted-pages and (2) log-structured.

Slotted Pages: Page maps slots to offsets.

Most common approach used in DBMSs today.
Header keeps track of the number of used slots, the offset of the starting location of the last used slot, and a slot array, which keeps track of the location of the start of each tuple.
To add a tuple, the slot array will grow from the beginning to the end, and the data of the tuples will grow from end to the beginning. The page is considered full when the slot array and the tuple data meet.

Tuple Layout

A tuple is essentially a sequence of bytes (these bytes do not have to be contiguous). It is the DBMS’s job to interpret those bytes into attribute types and values

Tuple Header: Contains meta-data about the tuple.

Visibility information for the DBMS’s concurrency control protocol (i.e., information about which transaction created/modified that tuple).
Bit Map for NULL values.
Note that the DBMS does not need to store meta-data about the schema of the database here

Tuple Data: Actual data for attributes.

Attributes are typically stored in the order that you specify them when you create the table.
Most DBMSs do not allow a tuple to exceed the size of a page.

Unique Identifier:

Each tuple in the database is assigned a unique identifier.
Most common: page id + (offset or slot)
An application cannot rely on these ids to mean anything

Denormalized Tuple Data: If two tables are related, the DBMS can “pre-join” them, so the tables end up on the same page. This makes reads faster since the DBMS only has to load in one page rather than two separate pages. However, it makes updates more expensive since the DBMS needs more space for each tuple.