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...
Thinking about Closure and LSMs
Math, specifically algebra, has some very nice interfaces. The idea that to perform operations on groups you simply take two of its elements and bash them...
The Little Planner Chapter 4: A Pushdown Party
Hi everybody, apologies, I didn't have time to put together a newsletter this week. In lieu of that, I found this chapter of a book called "The Little...
Simplifying Expressions Bottom-Up
There's a technique for simplifying expression trees that I learned from an old manager of mine, have never seen elsewhere, and have never shown to anyone...
Independence and The Futility of Cardinality Estimation
The official NULL BITMAP position is that query planners exist to approximate domain knowledge. That is, they're tools to replicate the knowledge of an...
A Left-to-Right Mental Model for Datalog
Note: see the end of this post for some housekeeping on last week. I get the sense that datalog scares a lot of people off. And I get that people might not...
SQL Scoping is Surprisingly Subtle and Semantic
It is not my intention with NULL BITMAP to dwell forever on somewhat obscure, unintuitive SQL-isms, but...with that said, I know a lot of you out there are...
Databases are not Compilers
Last week's issue was the topic of some contention in some of my circles. The general question was, is the following transformation valid: SELECT count(*)...
The Case of a Curious SQL Query
Languages that suffer success often have to do so by selling out and adding features that go against some of the original purposes of their design. SQL is a...
