NanoDB

CS121 - Relational Databases and Database Systems

What actually happens after you type in a SQL query and hit ENTER?… and why is it still running after 15 minutes!?

Taking Prof. Ordentlich’s Database Management Systems class, I finally gained an entirely new perspective and appreciation for the complexity that lurks just beneath these questions, and had so much uncovered to me about things I’d only ever taken for granted before. I mean, if you were tasked with finding all the employees in New York who make a salary greater than the average salary at their respective company, how would you actually go about that?

That’s how I really came to appreciate what a database system actually has to do, and below is just a quick overview of some of the things I uncovered, many of which I’d never even thought about before, along a whistlestop tour of the life cycle of a query.

  • Storage: Our very first assignment was implementing a slotted-page and heap-file organization structure… and until I actually got a sense of what this layout looked like in my mind, it felt like I may as well have been rummaging around a library entirely in the dark. Because I guess the nice and hard thing about systems is that unless you actually understand what’s going on physically, you really won’t get very far.

    The way I came to wrap my head around it was by thinking of disk memory as a town, divided into streets (pages) which house numerous residents (records or tuples, i.e. the actual row data in our database). There are really two scales at play here: the organization of the pages themselves, and then the internal organization of the tuples within each page.

    I found the slotted-page idea especially interesting. Each record has a slot which acts as a stable reference to it, while the actual tuple data can move around within the page as records are inserted, deleted, or compacted. So the physical data can shift, but the external reference to it remains stable as long as you update where the slot points. That’s what I mean when I say you need a clear mental image of the system, because otherwise keeping track of offsets, slot numbers, byte counts, and what needs to move where very quickly becomes chaotic!

  • External Algorithms: How do you manipulate data that can’t even fit entirely into memory? That’s a problem databases run into very quickly, and it’s handled using external-memory algorithms, where we have to interact with disk rather than keeping all the data in RAM at once. Since those disk trips are expensive, we have to be efficuent about how many reads and writes we incur, which is how we ended up studying algorithms like external hashing, external sorting, and block nested-loop joins, which we implemented ourselves for executing joins in our database.

  • Query Planning: At the very start of the course, we began with the theoretical idea of relational algebra, representing a query as an expression built out of operations such as projection, selection, and joins. What I found really satisfying was seeing that this abstraction gets mirrored almost directly in the implementation.

    A query is first parsed into an AST which we traverse, and from that we construct a query plan, itself a tree where each node represents either a raw table or an operation such as a join or projection. As the query executes, those nodes produce tuples whose output gets fed into the parent node, and so on up the tree.

    Some of the trickier parts came from recursively unpacking nested FROM clauses or handling aggregation, where references and aliases may refer to aggregate quantities rather than the original table schema. This meant pre-traversing the query AST so that those references remained consistent later when we actually executed the query.

  • Statistics Collection: One of the most important things I came to learn is that optimizing a query means making the most of all the information you know about your data.

    Take the New York salary example above. Imagine you somehow knew that the maximum salary was equal to the minimum salary across all the relevant records. You could instantly conclude that everyone earns the same amount, so nobody earns more than the average, and your answer is just zero rows. You don’t need to blindly execute every possible operation if the data itself already tells you something useful.

    The same principle applies more generally. If we know how many tuples a relation contains, how many distinct values appear in a column, or the minimum and maximum values, we can estimate how many tuples different predicates or joins will produce and therefore estimate their execution cost. Those statistics also change as we move through the query plan, so I implemented statistics collection which tracked minimum and maximum values, numbers of distinct values, and estimated selectivities under assumptions such as uniform distributions, and then propagated those estimates through the plan.

  • Query and Join Optimization: There may be many logically equivalent ways of executing the exact same query, but with drastically different computational costs.

    For example, if we can apply a selection earlier in the plan, then we shrink the number of tuples that every later operation has to deal with. That’s the idea behind “pushing down” predicates. Similarly, if we have to join several tables, the order in which we join them can completely change the size of the intermediate results and therefore the total cost.

    Using the statistics I collected, I implemented a dynamic-programming approach to join optimization based on the System R method, along with other logical optimizations of the query plan. Sometimes the way we naturally write a query does not align with the optimal way to execute it, so the optimizer’s job is to turn that expression into an equivalent one which costs less. After implementing this optimizer, a (purposefully poorly written) query which previously would not finish even after 30+ minutes could not be executed in just 1.7 seconds!

  • Indexes: Like I mentioned before, there are much more efficient ways of searching for keys if you know a little bit more about them. For instance, if you know your keys are unique, then doing a linear scan through all of our data just to find a single match may not be the most optimal approach. That’s where B+ tree indexes come in, which is a structure that lets us search and retrieve those records much more efficiently. (Of course, the tricky part is keeping track of the insertion and deletion logic, which is what had to write ourselves). I think indexes are especially cool because, on one hand, they come about from a very practical engineering need to make searches faster, but actually solving that problem requires an entirely different representation and conceptualization of how we organize our data.