Lightweight Cardinality Estimation with Density
Last week we talked about the different ways we can decompose a simple predicate which is a conjunction of two simpler predicates. Given the query: SELECT *...
Predicate Decomposition
One of the fundamental things that query planners have to do is decompose predicates. What do I mean by that, well, it's actually something that comes up...
More Data Independence and the History of the Relational Model
Last week we talked about some of the reasons why we want data independence. This week I want to talk about some of the historical steps that brought us to...
Data Independence
You and your bud are jamming out to math rock at the office while you work on the MVP of Datablaster 3000 and then the senior engineer walks in to the office...
Ordering and Partitioning
I've recently been downsizing my Magic: The Gathering collection to cards that I really want to keep. I think a "collectible card game" is a good way to...
Query Plan Caching
Serious NULL BITMAP heads know my love for the Query Plan Diagram. This is a 2D-rendering that represents the selection of plans for a particular shape of...
Lowering in Reverse
Recall last week, we talked about how to take a SQL query and turn it into a lower level plan, so this week I want to talk about how we can generate SQL...
Lowering in SQL
In the land of compilers, going from a higher-level representation of a program (that's easier for a human to author) to a lower-level representation (that's...
The Death of Thread Per Core
Programming language async runtimes are very focused on handling asynchronous, possibly long running tasks, that might yield for a variety of reasons, that...
Ordering types in SQL
A common problem that comes up in apps that use relational databases is the need to maintain some kind of user-defined order over rows. Imagine you have a...
Self-Extracting F3
Like everyone else who knows what a "row group" is, I spent some of last week looking into F3, the new columnar data format out of CMU. To take a step back,...
Another Sampling Technique
I am in the midst of moving, so here is another short post! Last week, we talked about how to use rejection sampling to sample possible complicated...
I Misunderstood Rejection Sampling All This Time
If you’re like me, you have cobbled together an understanding of statistics following your mediocre second-year stats class by watching YouTube videos and...
Infinite Relations
Let's write a super simply query engine using the iterator model. Something like this is conceptually what the compilation target for something like SQL...
Query Operator Structures
The way we usually like to think about operators in query plans is that they're just representative of "result sets." In the Volcano model, they're just...
Should We Have Been using LLMs for Our Test Queries This Whole Time?
Longtime readers of NULL BITMAP will know that I am bullish on metamorphic and in general, property-based testing for things that are SQL-shaped. I generally...
Some Stuff I've Been Reading
I’ve been on vacation and I don’t really have an exciting post to share, but I have been reading some, so here’s a bit of my reading list, and maybe you will...
Discrete Distributions
For a while now, my favourite piece of technical writing has been Darts, Dice, and Coins: Sampling from a Discrete Distribution by Keith Schwarz. In it, he...
NULL BITMAP Two-Year ZINE Special
It has been (about) two years of writing NULL BITMAP! Thank you for reading. This issue is very special because it contains none of my technical writing, but...
Diagrams For Yourself
I have a large need of diagrams. In particular when I'm writing something longer about a query planning topic I often would like some kind of standardized...
