Not all Graphs are Trees
It's pretty easy to imagine how to represent relational algebra expressions as a tree—they are already structurally rooted trees where each operator has its...
Heath's Theorem
We don't have all that much in the world of relational query planning that could be considered a "fundamental theorem," as in like, some central idea that...
The Geometry of SQL
Today I want to talk about a way to think about some relational algebra operations. First, let's start with this relation: This is just a handful of games...
My First Distributed System
I can show you a picture of the first distributed system I ever used: (Not entirely accurate, I had a Game Boy Color.) When I was a kid, we'd spend summers...
A Sniff Test for Some Query Optimizers
One important part of query planning is performing transformations over queries. Today I want to see how a couple common databases perform on a completely...
When Compositionality Fails
The idea of abstraction is that we can take some complex thing and present it as some simpler thing. Where people can ignore the aspects of the thing not...
So You Want to Generate SQL Queries (me too)
We have talked before about how to appropriately test query planners. I wrote there: I love metamorphic testing for SQL databases because it in large part...
CAP is Good, Actually
It seems like there are two main takes regarding the CAP theorem online: In introductory materials, it is presented as a deep, fundamental truth about...
A Very Basic Decorrelator
Today we're going to begin implementing a simple query decorrelator. We're not going to finish it in this post, and I'm not sure how many posts it will take,...
Some of My Favourite Query Planning Papers
Something I've learned about programmers is that for some reason they absolutely love being recommended papers. They lose their minds for it. So here is an...
The Three Places for Data in an LSM
We have talked before about how to conceptualize what an LSM does. I want to talk about another way to think through how we put together this data structure....
Physical Properties #3
Last week we walked through how a query optimizer might use Physical Properties to optimize a query plan. This week, I want to talk through one surprising...
Physical Properties #2
Last week, we talked about the idea of physical properties, which are attributes of a result set that, in some sense, do not have bearing on whether that...
Physical Properties #1
I wanna talk about relational algebra. Specifically, the things relational algebra is not concerned with, but obviously matter. Things like: ordering of a...
Testing Query Planners
A thing I did not appreciate for a long time is how different pieces of software merit different testing methodologies. I don't necessarily mean like, a...
Why SQL is Unkillable
My Twitter bio is it is easier to imagine an end to computing than an end to sql. I've thought a lot about the question of why SQL is such a cockroach. It...
Certificates and Duality
I wanna talk about optimization. Not query optimization, or program optimization, today, but the other kind. Mathematical optimization. Like when your high...
Reification and Exchange
One thing I really like about the parse-plan-execute cycle of queries is the ability to reify various computations in a way that are often invisible, or hard...
Should you read about "Database Theory?"
Hello! I am traveling and also sick and also this post is scheduled to come out on Christmas Day so it's going to be a little shorter and chiller than usual....
Tiering vs. Leveling
Last week we talked about how to think about "what is going on with LSMs." Today, we are going slightly deeper and a little bit sideways to discuss a design...
