Underneath any end-user database is another database and so much complexity arises from the challenge of building a database inside a database. Solutions to this problem vary widely and make some sort of trade-off between scalability (performance) and complexity.

Some applications load the entire end-user database in-memory. This creates long initial load times, but really performant interactions once the application loads. There are obvious scalability issues with this approach, but it is fairly simple to implement.

Other applications resort to O(n) scans on the server to fetch data and filter/sort records in memory with a few caching and indexing optimizations when convenient. The problem here is that users can create their own columns and filters dynamically. If your cloud application is backed by a SQL database, for example, it’s worrisome to allow users to edit the database schema and create an unbounded number of tables and indexes. Thus, you must resort to filtering records in-memory.

If you’re dedicated to O(log n) queries, you’ll need to build indexes yourself (unless there’s some amazing database I am unaware of). On every write, you can compute what indexes need to be updated and you write to a NoSQL database to incrementally update a cached query result. This can lead to a good solution, but it comes at the cost of consistency. Now that you’re building your own indexes outside of the database, writes are no longer transactional and you lose the guarantee of being able to read your own write.

Another solution is to have a separate database for every user and allow users to edit the schema of their own isolated database. This allows writes to be transactional, but creates other kinds of collision problems (i.e. dealing with merge conflict) when you want users to be able to collaborate. With separate databases for each user, you’re also doing a lot more computing labor, especially if the same records are shared amongst many people.

Long story short, existing databases are not great for building end-user databases.

You’ve probably experienced frustration with this when looking at files in your filesystem. Natural sort solves this problem elegantly by representing both alphabetical and numerical sort at the same time.

Representing numbers as lexicographically sortable is another interesting challenge, particularly very large and very small numbers. Elen is an interesting approach for encoding floating precision numbers.

Tuples can be represented as compound sortable by separating each item with null-byte (and escaping null-bytes inside each item).

Fractional sorting is a very related and interesting topic as well.

There is a direct analogy here with SQL. The Badge # cabinet is the officers table with the badge number as a primary key. The Precinct cabinet is an index on the officers table.

And the procedures list is just the list of SQL indexes on the officers table defined by the database schema that internally needs to be updated whenever an officer is updated.

This procedures list will also include SQL triggers on the officers table. While SQL does not let you create indexes on information joined across tables, you can effectively achieve this with triggers.

The trade-off we just considered by intuition is exactly what a SQL database’s query planner does. The query planner uses heuristics about how distributed the data is in different columns in order to choose which index to scan that will have the smallest amount of results.

That said, heuristics aren’t perfect and it’s totally possible that there are more officers with last name Smith than the number of officers in any given precinct.

This abstraction is a fundamental limitation of SQL and most database systems. In SQL, every trigger goes into a procedural list, even conditional triggers. This means that every additional trigger is going to linearly slow down every write.

You can do things like keep the list of auditor addresses in a separate table rather than create a bunch of triggers, but what you cannot do in SQL is have a dynamic list of stored procedures with efficient lookups.

I think there’s a very pragmatic reason for this as well: without a static list of procedures then it’s difficult to predict the performance of a write without actually trying to do it, looking up the procedures, and seeing how much work it’s going to be. With a static list of procedures, you can at least look at the length of the list to understand how much work is involved.

From a SQL perspective, this is similar to creating a trigger on an index (you can’t do this, but you kind of can if you generate indexes yourself with separate tables), creating a hierarchy of updates and thus eliminating some wasted effort. Furthermore, we’re creating conditional procedures that can be efficiently queried.

It’s possible that we want to listen to changes for an entire precinct, not just a specific person in a precinct, and we can use this same Precinct and Precinct Procedures cabinets to do this if we generalize how this works.

Suppose we want a procedure to run for updates to precinct 51 for any name. We can add a procedure sorted by the tuple [51] which comes before [51, A]. And when we lookup procedures, for [51, Colombo], we just need to make sure that we lookup not just [51, Colombo] but for all prefixes a well — in this case, [] and [51]. Note that [] means “any change to this filing cabinet”.

From a technical perspective, there are a few important things we should consider from this analogy.

For one, there are no database systems I am aware of that efficiently query and evaluate user-generated procedures. This kind of flexibility is essential to build a scalable end-user database application.

Another thing to consider is how information is sharded. In this analogy “sending something in the mail” is effectively saying that there is a boundary between shards. That is, the HR department and the Finance department are in different physical locations.

When we’re building applications for our users, where do all these filing cabinets live? One way to do it is if everyone has their own filing cabinets at home (and some people do). Another way to do it is every service you use keeps records of your information and you have to ask them for it whenever you want to see it. This is currently how most things work in the world: your health records live at your doctor’s office, the blueprints for your house live at the building department, and your emails live in a virtual filing cabinet in a Google data center.

This way of doing things is actually quite convenient for many people — they don’t need to keep track of their own records at all! On the other hand, it means people are less empowered to build their own filing cabinet systems to manage and automate their life. It also means that their information is less private.