One of the most useful classes I took during my time here at Penn State was CMPSC 431W: Database Management Systems. Amazingly, this is one of two classes offered by the CS department here on databases, and it is not required to graduate. The only required class isn’t a database class, but a Java programming class that teaches students about basic SQL since one of your projects uses JDBC to connect to an extremely rudimentary database and requires basic knowledge of implicit joins and creating tables with a GUI. So, for a while, I thought databases were easy and once you knew how to type SELECT ... FROM ... WHERE ...; you knew all that a non-DBA needed to know about them.

When I took 431W, I was told by past students that the class has you build a basic web application with PHP or something and then hook it up to a database to display a list of data on a page, like video games or food and you learn that if you change the content of the database tables, the list changes (wow!). However, when I got to the class, the instructor was different and we had a new project: design a database for a specific use case (nurses in a hospital) and then implement a simplified relational database management system ((R)DBMS, like a MySQL or MariaDB) in C to run the SQL code you wrote to create and query this database.

Certainly a taller order than the previous semesters had led me to believe.

So I went through the semester and learned all about how DBMSs work and the general algorithms behind performing SELECTs and JOINs and how there is infuriatingly no right way™ of doing things in the world of structuring a database. And while I learned that database administrator was an entry that I would strike off my list of desired careers, I also learned a lot about making database code more efficient and what would be useful for a developer to know as well as what you could probably get away without knowing. Here’s a simple list the major takeaways I got from the course, in case your CS department overlooks this stuff, like Penn State’s does.

## Where does the data come from?

There’s really only two ways to store data on a computer: memory and the disk, and since databases store very large amounts of data, they opt for the disk. A DBMS essentially keeps track of its records across files, then pulls the data out of the files and into memory for you when you need them. Now, it could just use the filesystem management built into the operating system and rely on the OS to manage its in-memory pages, but databases work differently than most other file use cases, so DBMSs re-implement their own paging algorithms. You don’t have to know how they work, just that it’s not literally using plain old file operations. Also, this is an oversimplification of how everything works aimed at showing how you could write a very simple DBMS, not how production code for any commercial SQL database software works.

Database tables are stored in a flat binary list of records, which are of fixed length. The record length is known since the columns in a relational database table are of a fixed type with an assigned length, hence why you have to declare a VARCHAR length, for instance. So, if you had a table of students with columns fname of type VARCHAR(10), lname of type VARCHAR(25), age of type INTEGER and student_id of type CHARACTER(10), then you would know that —assuming characters are 1 byte and integers are 4 bytes—that each record has a total length of 10+25+4+10=49 bytes and that the first 10 bytes of the record corresponds to fname and so on.

Keeping with this example, when you type a SELECT statement, you can move record by record until you match the WHERE conditions (knowing where to look by the byte offset), then return the corresponding record(s). Again, this is a very simplified look at things, but hopefully can tell you a bit about what goes on under the hood.

## How Should I Structure My Data?

Designing your data model is a very complicated process with no correct answers and a lot of trade-offs, and is totally dependent on your situation. However, if you want a collection of hard and fast rules on how your tables should be laid out, you most likely want to fit the database normalization forms. There are a lot of form orders, but you pretty much never need to go past third normal form (3NF).

### First Normal Form (1NF)

Let’s say you are storing a list of customers in a database, specifically their first and last names and their phone numbers (and an ID column that is the PK). At first nothing seems wrong with this design, and you can add a few customers with their respective information:

First Name Last Name Phone Number
Dale Cooper (798)-456-7910
Audrey Horne (465)-867-5309
Harry Truman (832)-483-0929

However, now we have to add Bobby Briggs, who’s a wonderful guy, but he recently signed up for cable or internet with Comcast or something and they threw in a free landline and hey, who doesn’t want a free landline? So now he has two phone numbers and wants to provide both, but you only have one phone number column, so you just serialize it as two numbers, comma-separated. Now you have this:

First Name Last Name Phone Number
Dale Cooper (798)-456-7910
Audrey Horne (465)-867-5309
Harry Truman (832)-483-0929
Bobby Briggs (383)-284-3892,(203)-382-1121

That new cell in the bottom right is not compliant with 1NF; it’s bad database design, since now if you wanted to query for customers with the phone number (203)-382-1121, it wouldn’t return anyone, since Bobby’s “phone number” is seen by the DBMS as “(383)-284-3892,(203)-382-1121,” which is not equivalent. If you want it to work as intended, you have to write a LIKE SQL query and have your application code handle parsing the results and make sure the developer intimately knows the table structure so that they also write all of their applications to do this too, and it just turns into a big mess.

Put simply, first normal form requires that each table cell is atomic, holding only a single piece of data that isn’t serialized and doesn’t mean anything other than what it says. To make our example comply with 1NF, you could split the “Phone Number” column into “Mobile Phone Number” and “Home Phone Number,” for example.

### Second Normal Form (2NF)

A table is in second normal form (2NF) if all of its non-key columns are dependent on the primary key and no other candidate key. Essentially, this means that for any row in the table, if I want to know a non-key column value, I have to know the PK value and can’t rely on any other column (or set of columns) that is unique for every row.

For example, let’s say we have a table of big-wigs at tech companies in a table:

Name (PK) Company Position Location
Satya Nadella Microsoft CEO Redmond, WA
Tim Cook Apple CEO Cupertino, CA
Bill Gates Microsoft Co-Founder Redmond, WA
Jeff Bezos Amazon.com CEO Seattle, WA

Here, we see that {Name} is the PK, but the combination {Company, Position} could also be a PK, and location depends on part of that candidate key, specifically Company. This is a violation of 2NF. To fix it, break out the table into 2 tables:

#### People table

Name (PK) Company (FK) Position
Tim Cook Apple CEO
Bill Gates Microsoft Co-Founder
Jeff Bezos Amazon.com CEO

#### Companies table

Company Name (PK) Location
Microsoft Redmond, WA
Amazon.com Seattle, WA
Apple Cupertino, CA

This accomplishes a couple things: firstly, it makes our data returned a bit cleaner; if we want to know who the CEO of Microsoft is, we should get Satya Nadella, and if we want more information about him, I can look it up elsewhere in the database. Second, it removes an unnecessary dependency in our People table between company and location. Now, if Amazon moves headquarters, we don’t have to update every row with Amazon as the company in the table, we just have to update the location in the Companies table and the rest will take care of itself.

### Third Normal Form (3NF)

Now that we’ve removed any dependencies on a partial candidate key, we want to remove any dependencies on any column in the table that isn’t the primary key. This is pretty simple to spot, as shown below, in the table below:

Game (PK) Winning Team Winning Team Location
Super Bowl XLIX Patriots New England
Super Bowl 50 Broncos Denver
Super Bowl LI Patriots New England

Spot the issue? The game name is the primary key (and it is the only candidate key), but the Winning Team Location column doesn’t depend on it or any candidate key, it only depends on the Winning Team column. That’s a 3NF violation, and we can fix it by moving Teams and Super Bowls into different tables:

#### Super Bowls

Game (PK) Winning Team (FK)
Super Bowl XLIV Patriots
Super Bowl 50 Broncos
Super Bowl LI Patriots
Super Bowl LII Eagles

#### Teams

Team Name (PK) Location
Patriots New England
Broncos Denver

Similar to 2NF, we’ve now removed redundant data from the Super Bowls table, so if we ever need to change a city associated with a team (say, if they move), we only have to update it in one place. Makes sense, right? You should always do this, right?

Right?

Wrong. There are situations where the cleanliness and theoretical perfectness of these normal forms are outweighed by a practical concern: in a lot of cases, NFL teams are written in the form [City] [Team] (i.e. “Philadelphia Eagles” is far more common than “Eagles”). In order to get the data out of the database to display it on, say, a scoreboard, you need to perform a JOIN between the Teams and Super Bowls tables, which is slower than just grabbing the rows out of the Super Bowls table. And let’s be honest, NFL teams moving is pretty rare, so you can afford to update at most 6 rows in a database if the Steelers move cities. So, it may make more sense to just keep the location in the Super Bowls table when it comes to practical performance.

## What in God’s name is an index?

The following may be a conversation you may have (or had) at some point during an internship during your college career (I certainly had it happen at least once):

You: “Gosh, this database is slow!”

“Real” developer: “Yeah, maybe we should index this table.”

You: “Heh yeah, good idea. That might help…”

And then you go do something else (or get the “real” developers coffee, if you work at a shitty company) because you have not the slightest clue what an index is, what it does, or how it will make your database calls faster.

Let’s demystify indexes a bit. Remember that database data is stored in files, and we’ll even go so far as to pretend that a DBMS can access all of the data in memory. So, if there’s an array of data and you’re searching for any item that satisfies some condition (i.e. a SELECT...WHERE clause), you could perform a linear search if the data is unsorted since the DBMS has no way of guaranteeing that it didn’t miss something along the way than checking every single row’s values, and—as you learned in CS 101 (or CMPSC 122, for my fellow Nittany Lions)—linear searches are kind of slow since they have, well, linear time complexity. And God forbid you want to perform a JOIN, then you’d have nested loops!

The other way you could search the data is by taking your flat data and putting it in some sort of data structure, then using a more efficient searching algorithm on that structure to find what you’re looking for in sub-linear time. The process of putting the data from a table into one of these data structures is exactly what indexing is.

For example, if we have a table of students with columns for their student ID numbers (the primary key), first name, last name, and starting year, then our table would be sorted by student ID number, since that’s the primary key. And that’s all well and good until someone wants to write a web application for TAs to enter grades by last name rather than ID number because its more convenient. At that point, it would make sense for you to index the table. When you do, the DBMS makes a table that is sorted by last name and has mappings for each row of the form (last name => student ID). Now we can find the info for a student by finding their last name in the index table, then finding the corresponding entry to the primary key in the original table, and just like that our search is executed in log(n) time.

This is a rudimentary example, and real DBMSs have a plethora of data structures that they can make indexes from. Two of the most popular indices are hashes and B+ trees, and they both have different use cases. Are you checking for equality, looking for one specific row? A hashmap may work best. Looking for a range of values with more relative comparators? A B+ tree should do the trick.

### Index all the things?

So right about now indexes are probably looking pretty damn sweet. In fact, you might be tempted to index everything in every database you ever make. Do not do this. Indexes (or indices, I don’t know which is correct) do speed up reads pretty significantly, but they also slow down writes. Why? Well, since they are essentially copying a subset of their table’s columns, they have to be updated (and sorted!) whenever a new row is added to the table or a row is updated that involves the columns being indexed.

In our example above, every new student would have to be inserted into both the original table and the index, and not only that, but inserted into the correct place in the index, since the data is sorted. Now, since students are only inserted rarely (twice a year, say) but read far more often, this may be a good trade-off to make. But, it’s something to think about.

That, right there, is the biggest takeaway I had from my databases class: data model design is less about what the best way of doing something is and more about what the best way of doing it given the current situation is. If you learned one thing from this post, I hope that’s it.

And if that sounds horrible, then I hope you—like me—also learned that being a database administrator is not your calling.