End-user databases are all the buzz these days — Notion, Airtable, Coda, Roam, etc. These products have made it possible for people to model information in a way that feels more natural and intuitive to the way we experience it in our daily lives.

I love building products like Notion, but building these kinds of products is hard. For two reasons:

This second challenge is more technical and I will hide all of these programmer-related details behind a toggle so you don’t have to read them if you’d like.

I plan to address this first reason by giving you a mental model of what databases are and a first-principles understanding of how they work.

I’ll introduce databases as an abstract concept and then we’ll work through a real-world example to explore how databases leverage sorting and filters to lookup information quickly.

By the end, I hope to show you how these information architecture concepts are immensely powerful and totally approachable for non-technical people.

Lastly, I want to convince you that software based on these concepts will be far superior to anything we use today for end-user database applications. If these concepts are interesting to you, please reach out! I love sharing ideas. 😁

Databases are filing cabinets.

Databases don’t have to be so complicated. If you strip away all the fancy semantics, you end up with something simple and familiar.

Dictionaries, calendars, and filing cabinets are particularly useful because they represent information in a sorted order, making it possible for us to retrieve information quickly and efficiently using a process called binary search. Databases are no different, they’re also containers of sorted information.

Alphabetical, numerical, compound, lexicographical Encodings.

The simplest way to sort something is alphabetically (a.k.a lexicographically) and this is how words are sorted in the dictionary. But we often find ourselves sorting by more than one property. For example, a contact list is often sorted by last name, then first name. This is called a compound sort.

For example, notice that “Thomas Robins” should come before “Charlie Robinson” when sorting this way and that a compound sort is fundamentally different from simply joining the words together and then sorting.

We do this kind of compound sorting all over the place. Dates, in particular, are compound sorted by year, then month, then day.

Notice that this kind of sorting isn’t exactly alphabetical. The months in a year are definitely not sorted alphabetically — each month has an underlying order within a year. Even days of the month aren’t alphabetically sorted — they’re numerically sorted.

Numerical sorting is different from alphabetical sorting because alphabetical sorting compares letter-by-letter. For example, if we sorted numbers alphabetically, then 10 would come before 2 because the first digit “1” is before “2”.

A simple way to represent numbers in a way that can be sorted alphabetically is to put zeros at the beginning of the number. This works well for small numbers with a known maximum size such as the months in a year.

And in fact, we can represent dates in a way that can be sorted alphabetically using ISO 8601 date format.

Representing dates this way is convenient because it doesn’t require domain knowledge to understand how to sort them. There are an infinite number of things that can be sorted arbitrarily: a deck of cards, the status of a project, your rock collection—they are all just different types of things.

In general, lexicographical encodings are important because they allow databases to store arbitrary information in the correct order without needing additional knowledge about the type of information that is being sorted.

You can think of databases much in the same way you think of system filing cabinets. To explore this analogy further, let’s imagine that you are in charge of administering a police department where you keep track of a variety of information about every police officer in your region — name, badge number, address, and precinct, among other details.

As the administrator of this information, you’re responsible for making sure that everything is up to date and easily accessible.

To keep things simple, you start by keeping all officer information in a filing cabinet sorted by badge number. This makes it easy to retrieve information about any officer based on their badge number, for example when an officer gets promoted or moves to a new address.

How we copy information into other cabinets.

One day, the police chief asks you for the address of every officer in the 60th precinct.

With all of this information in a single filing cabinet sorted by badge number, this is a painful request because you have to scan through every file and check if each officer is in the 60th precinct.

Maybe this is just a one-time request so you can labor over it and be done with it, but the police chief says that every month he wants to mail a bonus check to every officer in the precinct with the most arrests. If you’re going to have to do this every month, maybe it’s worthwhile to make this job a bit faster.

To solve this problem, you create another filing cabinet where you sort all officers by precinct. To keep things simple, you photocopy all of the information in the Badge # cabinet over to the Precinct cabinet. Now when the chief asks you to get the address of every officer in a precinct, you can use this new filing cabinet to quickly retrieve the information.

This new filing cabinet makes it easier for you to get information, but you’ve created a new problem every time you have to update the information. If a new officer joins a precinct or an office moves from one precinct to another, you now have to make sure the information is correct and updated in two different places.

Making things worse, we end up wasting time keeping unnecessary information up to date. For example, maybe we don’t need the date of birth or a photo of the officer in the new Precinct filing cabinet we made, but we copy it over anyway so the information doesn’t get out of sync.

On the other hand, maybe we decide that the only information we store in the Precinct cabinet is the badge number. This makes changing and managing information about the officers require much less work — we only need to update it in the original Badge # cabinet. It also means that the Precinct cabinet is much smaller because we don’t have as much information crammed in there.

But there’s a catch. Now if you need to get the address for every officer in a precinct, you’ll have to first use the new filing cabinet you made to get the list of officers in the precinct and then you’ll have to use the original Badge # filing cabinet to get the address for each officer. This is still quicker than not having a Precinct cabinet, but not as fast as the previous approach for scanning through every officer’s file.

Fundamentally, there is no “best” way to do this — it’s all a trade-off between how much work you want to do when reading vs writing information.

There is a middle ground between these two approaches where we record both the address and the badge number in the new Precinct filing cabinet we created. This strikes a nice balance where we don’t have to update information that we don’t care about in the Precinct cabinet.

However, this does come with some logistical overhead — now we have a list of procedures we have to follow when updating the Badge # cabinet:

Determining how to answer a question with existing filing cabinets.

Now let’s suppose that whenever someone files a complaint against an officer, we want to make note of the complaint in the officer’s file. Often times, when someone files a complaint, they don’t have the badge number for the officer but they do have the name of the officer.

To make it easier to look up officers by name, we create another filing cabinet to sort all officers by name. Our filing system now looks like this:

Now let’s imagine this police department grows from 10k officers to 10M officers. You receive a complaint for Officer Smith with brown hair, blue eyes, from the 121st precinct.

You’re considering two different ways of looking up this officer — you can either scan through every officer in the 121st precinct looking for Officer Smith or you can scan through every officer with last name Smith looking for the officer in the 121st precinct.

You make an assumption that there are probably fewer people with the same name than there are people in the same precinct, so you decide to first look up the officer by name.

In databases, this process is called query planning: you have a question (some information you want to retrieve) and an existing filing cabinet setup, and you need to determine the quickest way to gather all of this information.

So you look into the Name cabinet that you created and end up finding out that there are actually hundreds of officers named Smith in the 121st precinct. Once again, you decide it’s worth figuring out a faster way to do this.

What you want is something like the Precinct cabinet that you created with a secondary sort by officer name. But the Precinct cabinet doesn’t include officer names, so you would have to create a new filing cabinet to include them. You decide it’s probably more efficient to just copy the officer names over to your existing Precinct cabinet and sort by name to save some space.

As we discussed earlier, this is a compound sort since we’re sorting on more than one property: precinct, then name.

Automating internal mechanisms.

In response to public outcry about skyrocketing officer complaints, the police department has hired local auditing firms to audit each precinct. Now whenever information about an officer is added or modified, we need to notify the auditing team assigned to the officer’s precinct about the changes.

We start to write out these procedures on the same list as before, but we start to realize that this is going to be a really long list of procedures.

Every time we make a change to the Badge # cabinet, we now need to scan through this huge list of procedures and it takes too much time. So what we do is quite simple, we move all of the auditor addresses into a new filing cabinet and add a step to our list of procedures that tells the clerk where to lookup the auditor’s address.

This is much more manageable, but as you can imagine, the procedure list will keep growing as the organization evolves in complexity; the HR department wants to know whenever an address changes or a complaint is filed; the Finance department needs to know whenever an officer is promoted so they can adjust their paychecks appropriately — the list of procedures goes on.

Hopefully it’s not too hard to see that this procedure list itself can be turned into a filing cabinet sorted by property. That way, we don’t need to read through every procedure for every property when we’re just updating an address. Therefore, whenever we make a change to the Badge # cabinet, we lookup every property that changed in this Procedures cabinet to see what we need to do.

So far, we’ve only maintained a list of procedures for the Badge # cabinet, but there’s no reason why we couldn’t have the same kinds of procedure lists for other cabinets. And in fact, it’s really useful to do so because it lets us partition our procedure list into more efficient ways of sorting procedures.

For example, suppose there’s an ongoing investigation where the FBI wants to know if there are any changes to officers in the 50th precinct with the last name Colombo.

We could create a procedure for the Badge # cabinet that checks whenever a name or a precinct changes, then checks if it’s the 50th precinct and last name Colombo.

However, there’s going to be a lot of wasted effort checking this procedure every time a precinct is changed. For example, suppose Officer Smith moved from precinct 60 to 61 — when you lookup procedures, you’ll see this procedure and need to check for Colombo in the 50th precinct.

There’s a better solution — we can create a procedure for the Precinct cabinet. Recall that the Precinct cabinet is a compound sort by precinct, then name. Thus, we can make our procedure cabinet really granular by using a compound sort for the procedures.

Now, when I move Officer Smith from precinct 60 to 61 (first cabinet in the image below), I will see a procedure telling me to update the Precinct cabinet, and after updating the Precinct cabinet, I will lookup procedures for the Precinct cabinet to see if there are any procedures for precinct 61 and name Smith. Notice that we are able to skip over the procedure that checks for precinct 50 and name Colombo. This is really efficient!

Procedure lists and being able to efficiently lookup what procedures you need to do when updating a cabinet is a really powerful abstraction for automating information systems. Even more, this abstraction goes beyond the capability of existing database systems.

Receipts, forms, requests to change information.

There comes a time when there are so many people and so much information changing that it becomes important to keep track of all the details around who is changing what and when.

For example, maybe you open up the file for Officer Jones and it says he is a detective. And maybe you thought he was just a deputy, so you might be inclined to ask questions like “when was he promoted?”, “who promoted him?”, and “how many promotions were there this year?”.

These questions are impossible to answer with our current setup and you can imagine that if you were administering a bank, you’d be asking these kinds of questions all the time about the movement of money between accounts.

At a bank, every transfer between accounts is going to be documented with some sort of receipt that gets saved forever. And at our police department, changing any information might be documented with some kind of form. For example, when the police chief wants to promote Officer Jones to detective, he fills out a “promotion form” and delivers it to the filing clerk at the administration office.

The filing clerk might put this form in a filing cabinet for promotion forms sorted by rank and then date. Then we look up a set of procedures for this promotion, one of which is simply updating the rank of the officer in the Badge # cabinet.

This process definitely requires more work than simply updating the officer’s rank in the Badge # cabinet, but it allows us to audit changes and answer a broader set of questions about how things have changed over time. For example, we can look at all promotions by rank over time from the Promotion Forms cabinet. And if we wanted to determine when an officer was promoted, we can create a separate cabinet that sorts these promotion forms by badge number, then date.

When keeping a historical list of changes for auditing purpose, it’s often important to build mechanisms to make sure that the information is not tampered with.

For example, suppose a bad actor wants to secretly add a record showing that Officer Jones was demoted on Dec 11 prior to being promoted on Dec 12 (perhaps to create a fraudulent scandal they can write about in the news to discredit the police chief before an election).

Signatures are the first line of defense here. If a signature is hard to copy, then it will be hard to create a fraudulent demotion form (note: we’re using the same promotion form for demotions as well). Another thing we can do is make note of the previous rank in the promotion form. That means if the bad actor wants to create this fraudulent demotion form, they will also need to fraudulently update the promotion form of Dec 12 to reference a previous demoted rank.

In the physical world, protecting against this kind of fraud is pretty difficult and inevitably requires some kind of trust in the system. But in the modern world with encryption and one-way hashing, we can create signatures for records that cannot be tampered with. This is exactly how the blockchain works to prevent fraudulent transactions in Bitcoin.

Permissions, asynchronous communication, consistency, conflicts.

At this point, we’ve pretty much covered everything that is interesting about filing cabinets and how we can use them to manage large amounts of information with operational procedures. But there are a few more important systems needed for any realistic administration department.

The first is managing permission. Who has permission to promote an officer? Who has permission to read the complaints on a given officer? And who has permission to change the address of an officer?

There are plenty of ways to manage this and most organizations use some kind of permission hierarchy to keep things simple. I will leave answering these questions as an exercise for the reader, but if you are technically inclined, I would recommend reading about how Google solves this problem with their Zanzibar database.

Another part of the system that needs to be carefully managed is how information gets mailed around to different departments. Sending something in the mail takes time which can cause all sorts of issues in a complex organization.

For example, maybe an officer gets promoted on Dec 12 and when the finance department sends out paychecks on Dec 13, they still haven’t received the promotion from the mail and so they send out a paycheck based on their previous rank.

Things get even more challenging when coordination is involved. For example, maybe the HR department determines that an officer has too many complaints and must be demoted. The HR department sends the demotion in the mail to the administration department as well as the finance department. At the same time, the chief thinks that the officer should be promoted and sends a promotion in the mail to the administration department as well as the finance department.

Now what happens? Regardless of the outcome, the most important thing is that the administration, HR, and finance departments end up with the same result (also known as eventual consistency). For example, if the finance department decides to process the promotion and the administration department decides to process the demotion, then their records will differ and the officer will receive a larger paycheck than the administration department expects.

These are hard problems to solve and I will leave it to the reader to think about how to manage these kinds of coordination problems. But if you’re technically inclined, I’d recommend reading about how Automerge deals with these problems for peer-to-peer software.

Databases can seem quite complicated, but every database fundamentally works just like a system of filing cabinets and stored procedures. Things start to get more complicated when we need to keep information up to date in many places and we want to have an audit trail of all changes to a database. But this complexity is essential to solving the problems we addressed.

When it comes to the future of computer literacy, I know that not everyone is going to be a ninja programmer, but understanding the details of how to structure systems of filing cabinets will allow ordinary people to get the most out of computers.

If you are inspired by these ideas, want to build an embedded database, or just want to toss around some related ideas, please don’t hesitate to reach out. Thanks for reading 🙏

Published January 12, 2020 by Chet Corcos

Thanks to Haris Butt and Max Einhorn for reading drafts of this. https://ccorcos.github.io/filing-cabinets/