Database Storage (Part II)

 Last article about part I, I discussed how to make a disk-oriented architecture, to support databases that are larger than the amount of memory that is available in a single machine. We finished up talking about slotted pages, which is how we're going to organize tuples inside of a page to move things around and pack in as many tuples as possible and reaching end to beginning in tuples and beginning to end slot array until there is not space. This is not the only way (but the primary way!!) that the database system is organized.

We can also do log-structured file organization. Instead of storing the full tuple inside of the pages, we just store the information on how that tuple was created or modified. We can also have a log records, which just allow fast sequential writes, as compared to random access. 

Sometimes when you read you need to see where to go back unless you compact the log, or build indexes to allow it to jump to location in the log, or you can convert things back in the tuple form (HBASE, Cassandra, etc).

The databases represent pages, and we can break the heap file into pages, and we want to represent data, and how do we store the metadata about the tables, and finally understand storage.

At a high-level a tuple is a sequence of bytes, and it's the job of the database management system to interpret those bytes into attribute types and values, and the catalogs contain the schema information about tables the system uses to figure out the table's interrupt. 

We represent data for fixed-length things, what we represent in C/C++ which is the IEEE 754 standard, which is the specification of how to represent numbers in CPUs (bits, big endian/little endian, two;s complement, etc.). 

There's a C/C++ representation in terms of INTEGER/BIGINT/SMALLINT/TINYINT and IEEE standard for FLOAT/REAL and VARCHAR/VAR/TEXT/BLOB as header with length and TIME/DATE/TIMESTAMP for the Unix epoch.

Variable precision numbers sounds like what we want to use, because it's fast. But the problem is there might very well be rounding errors. 

#include <stdio.h>

int main(int argc, char* argv[]) {

    float x = 0.1; 

    float y = 0.2;

    printf("x + y = %.20f\n", x + y);

    printf("0.3 = %.20f\n", 0.3);

}

Here are the corresponding outputs when you specify to 20 bits: 

You start to care about rounding error if there is a bank account, or if you're trying to send something to space. There's fixed precision numbers. The way/idea to do this is to store the value as a VARCHAR and let the metadata to say the decimal/scope/rounding information. POSTGRES also can run parallel queries. If you want to deal with rounding, the same queries will be extra slow as a result, we can try to cast things as a decimal, etc. Oracle will give you the fixed-point decimal no matter what. Oracle says if the size doesn't fit in the number of character, then it rounds it from you automatically. We can also round to a precision in MYSQL syntax. 

Postgres has a syntax for approximating the digits. Here it is: 

typedef unsigned char NumericDigit;

typedef struct {

    int ndigits;  number of digits

    int weight;   weight of first digit

    int scale;    scale factor

    int sign;     positive/negative

    NumericDigit *digits;     referencing the type, digit storage

} numeric;

The source code is basically a bunch of switch statements, and we're executing this code for every single time we compute this number. 

We use a fixed-point decimal if we don't want to lose data using inprecision. 

The size of the data is going to be fixed for most database managment systems. What do we do if the thing that we're trying to store doesn't fit in a single page? We'll just have a pointer to some other overflow page that has the data that we want. If we now have a query, we'll have to follow this pointer, copy the data out, and produce it as an output to chain them all together and produce the output that we're looking for. 

We can also store things in a filepath or a filepath on a local disk instead of just a external file. You can't manipulate what's in this file. You can read it, but you can't manipulate it. Ephemeral means reading the data and immediately discarding it. The BLOB type indicates a system that stores a really large value in the ephemeral file. 

You don't want to store the video in a database. Django, NodeJs, etc. have built in ways to store data outside of a database, for images and other things. There is no rule in how big a file should be. Overflow is transparent to the application, you don't know. In Oracle, this is a BFILE data type and for Microsoft, this is a FILESTREAM data type. This is in the case if the database storage is super expensive. 

Let's talk about how to figure out what our tuples look like. The DBMS stores the metadata about the database as well as user permissions and security stuff, so it basically stores the metadata of the databases. Every single DBMS is going to store their catalog inside itself, like eating your own dog food. You don't want to write SQL queries inside of the table. You usually have some C++ code/whatever your data system is programmed in to access a catalog. 

Most systems exposes the catalog to the standard information API. In ANSI and SQL they specify INFORMATION_SCHEMA that has the metadata about the tables, and they don't always expose the exact same information about these tables. We are converting commands to get schema: 

Postgres -d gets the list of all tables and -d+ gets more information and tells what the metadata of each table will look like. 

This is what the metadata looks like. So there's a collection, field type, key, and any extra data. sudo su will log into its root and the we can see go to where data is stored. 

You want to put as much as possible in the database system to rely on that to perform correctly for us. That's all we need to cover for this semester. We're going to use that for queries and indexes, etc. The way to think about this is that the easiest way to implement this is a giant switch statement. If a type is an integer do this and if the type is a float do that. 

You need to realize that the relational model doesn't say anything about how we actually want to store data, doesn't know about types, byte-on-byte array, or any of that stuff. So, so far in the class, it's hard to visualize databases. The revisions table is where we updates of the article, and the reference to the usuers and the pageid that represents the articles that we will change. 

 

There's online transaction processing, or OLTP. Queries are very simple and reading data, as well as updating a small amount of data. This is usually the kind of application that people build first.

OLAP, or online analytical processing is when you first collect data, and now you want to analyze it an extrapolate new information from it, which is data analytics, decision support, big data, along many other names. 

A query might be counting the number of people that have logged in per month where the hostname ended with .gov, like members of congress scrubbed and cleaned whatever scandals the congressman have. These queries are read-only, they're gonna read a lot of data, and does a lot of joins. 

SELECT COUNT(U.lastLogin),

    EXTRACT(month FROM U.lastLogin) AS month FROM useracct AS U

    WHERE U.hostname LIKE '%.gov'

    GROUP BY

        EXTRACT(month FROM U.lastLogin)

HTAP is hybrid transaction analytical processing is when you ingest new data but analyze it when it comes in. 

So now, given that we know about these workloads, we want to know the right storage model to support these workloads more efficiently.

MongoDB Cassandra and Reddis ingests new data. Mongo has support to do some analytics, but they are not a column store, and they are going to get CRUSHED by any column store database, or anything that runs on the column store system. 

Everybody but Mongo supports some variant of SQL. MongoDB supports full-fledged distributed transactions. SQL always come back and it's what people want. Every time a tuple was shown, I showed it as a row. 

In a n-ary storage model, the DBMS stores all attributes for a single tuple contiguously on the page. Ideal for OLTP where queries tend to operate on individual-entry and insert-heavy workloads. The amount of data we're going to access is going to be small for queries and to get all of the data for the account. 

The DMBS stores all attributes for a single tuple contiguously in a page. 

Most of the workloads are getting the data from single entities from NSM disk pages for like

SELECT * from useracct

    WHERE userName = ?

    AND userPass = ? 

    

INSERT INTO useracct

VALUES (?, ?, ..., ?)

We realize that we're going to have to touch the data for a full sequential scan of a query. 

SELECT COUNT(U.lastLogin),

    EXTRACT(month FROM U.lastLogin) AS month

    FROM useracct AS U

    WHERE U.hostname LIKE '%.gov'

    GROUP BY EXTRACT(month FROM U.lastLogin)

We want to see the last hostname and then group by some specific terms. We. look at tehe catalog and we want the hostname and we get to the end. 

Now we want to aggregate things together based on the login with the GROUPBY clause. So we want to get the number of employees that log in per month.

However, there's a problem. You have to read the entire page in non-volatile storage places. So we have all these accesses and a bunch of data. 

Doing analytics on rowstore is going to be painful if you have a lot of data because we are going to access all of the data. The advantages of row storages is fast inserts, updates and deletes and the disadvantages is it's not good for scanning large portions of the table. This is where column storage comes in so instead of all the attributes of a tuple in a single page, we're going to store the values of a single attribute accross all tuples in single page. 

This is where the column is, we're storing all the values of a particular column contiguously, and this happens if we only want to read a subset ina particular table. Now we can get the data of a partucular column contiguous lin a single page.

All we have to do is to bring in hostname page, and look at every singe hostname, and see the tuples that matched, then we go on to bring in the last login page and jump to the corresponding locations. 

All the attributes within a tuple are roughly different domains. If I can pack all this data, there are some compression techniques that can be done as a result, because I know they are all going to be the same type!

So, now I have a match in one page, how do i find a match in another page? Everyone has the first approach. There are 2 ways for tuple identification:

1. Fixed-length offsets

2. Embedded Tuple Ids.

In fixed-length offsets, each value is the same length for an attribute. The embedded ids, each value is stored with its tuple id in a column. 

This is the offset.

And here's the embedded id: 

›

In each value in the column, you store a primary key and the identifier for it. I want to get to tuple for column B and we want to find offset locations for tuples in the column. There's storage overhead tho, since there's an extra 32-bit id for every column, which is wasteful.

The advantage is to reduce the amount of waster I/O because the DMBS only reads the data it needs, but the downside is it is slow for point queries, inserts, updates, and deletes because of tuple splitting/stiching.

Column stores go back to the 1970s and there is a Swedish system called Cantor. The 1980s have more formal details for:

1. What does this model look like?

2. What are the implications for having these storage models?

It nearly got an adoption since it sold as an add-on to the register database. The underlying representation of the database is not something of the storage manager or not the rest of the system. So the next problem is how the DBMS manages its memory and move back and forth from the disk. For n memory we think we can do fast enough transactions on a column store, and it's a bit more complicated in for disks. 

So basically what people do is you have these frontend systems with MYSQL/Mongo and stream the data to a backend warehouse and you prune out the data, especially when you know that you don't need it anymore. 

By the way, here's what what a column store looks like, for reference: 

and for reference, the EXTRACT function extracts part of a given date.