NULL BITMAP by Justin Jaffray
It is easier to imagine an end to computing than an end to SQL. This newsletter is where I will write periodic self-indulgent articles on topics in databases, with a focus on query languages, query planning, and transaction processing. This newsletter is an extension of my blog justinjaffray.com. I
- Posts
- 150 from 14 Aug 2023 to 29 Jun 2026
- Posting
- weekly (42 in the last year)
- Kind
- personal blog
- Feed
- https://buttondown.com/jaffray/rss
2026 32
- There are Databases Everywhere for Those with the Eyes to See
- Divergent Histories
- Hash Consing Absolutism
- SmithDB
- Partial Pathfinding Applications
- Three Binary Tricks
- Lambda Diagrams
- Has Merge Join's Time Gone?
- The Moon
- Where Optimizations Come From
- Columnar Storage is Normalization
- More tools for testing SQL dialects
- Floyd's Sampling Algorithm
- Boyer-Moore Majority Element
- Pivoted Query Synthesis
- Solving Cryptic Crosswords with Egraphs
- Simulating Queueing 2
- Simulating Queueing
- Expectation Again
- Fortran Parsing Algorithm
- Expectation and Copysets
- Another Sampling Technique September 29, 2025 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...
- Mark Join
- Self-Extracting F3 October 6, 2025 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,...
- Online, Asynchronous Schema Change in F1
- Ordering types in SQL October 13, 2025 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...
- Delayed Code Generation
- The Death of Thread Per Core October 20, 2025 Programming language async runtimes are very focused on handling asynchronous, possibly long running tasks, that might yield for a variety of reasons, that...
- I deserve to write at least two or three more arithmetic expression parsers
- Lowering in SQL October 27, 2025 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...
- Menger's Horse Enclosure
- Lowering in Reverse November 3, 2025 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...
2025 46
- Inlining
- Query Plan Caching November 10, 2025 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...
- Unger Parsing
- Ordering and Partitioning November 17, 2025 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...
- Lightweight Cardinality Estimation with Density
- Data Independence November 24, 2025 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...
- Predicate Decomposition
- More Data Independence and the History of the Relational Model December 1, 2025 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...
- Multiplexing May 12, 2025 In the world of electronics, multiplexing is the process of taking a set of communication channels and collapsing them all to be transmitted along a single...
- Kicking the Tires on CedarDB's SQL May 19, 2025 Last week it was my birthday and I had a bunch of stuff going on over the weekend so a short and simple post this week! If you are a database sicko (and I...
- Building One to Throw Away May 26, 2025 I've been thinking lately about the nature of bespoke data structures for bespoke purposes. I think you learn fairly early on in most programming contexts...
- Edge Contractions and Join Planning June 2, 2025 The join graph of a query has a vertex for each relation and an edge between any two relations that have a predicate between them. For example, this query:...
- Nonograms June 9, 2025 Hello! I hope you are having a lovely day. This week I got distracted by some non-database content and it consequently took up a lot of my time. Usually I...
- Search Engine Retrieval June 16, 2025 I want to talk about the high level concept of what a search engine does. And I don’t mean like, Google, or Kagi, “the product,” but the technical object...
- Monotone Functions and Cache Lines June 23, 2025 If you've taken a calculus class your professor might have explained to you the idea of a monotone function, or (in one direction) a nondecreasing function....
- Caching is an Abstraction, not an Optimization June 30, 2025 I've always been told that caching is a tool to make software faster. That, given some careful considerations to consistency, caching makes it so that when...
- Unified Memory Management July 7, 2025 There's a trend in database memory management design that I'm really excited about, and that is rethinking the abstraction boundaries of the buffer pool. I'm...
- NULLBITMAPGPT July 14, 2025 I don't know if you've all been paying attention, but this is the ONE HUNDREDTH NULL BITMAP?? To celebrate, I've heard people are really into "next token...
- Bloom Filter Sizing July 21, 2025 Here's a question: say I have two streams of objects I want to construct Bloom filters over, one stream is red and one stream is blue and they're about the...
- Giving Benchmarks a Boat July 28, 2025 I've been thinking lately about this piece from Frank Lantz about the Thielian "the Olympics, but you take performance-enhancing drugs." The pitch being...
- Diagrams For Yourself August 4, 2025 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...
- NULL BITMAP Two-Year ZINE Special August 11, 2025 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...
- Discrete Distributions August 18, 2025 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...
- Some Stuff I've Been Reading August 25, 2025 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...
- Should We Have Been using LLMs for Our Test Queries This Whole Time? September 1, 2025 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...
- Query Operator Structures September 8, 2025 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...
- Infinite Relations September 15, 2025 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...
- I Misunderstood Rejection Sampling All This Time September 22, 2025 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...
- Git Workflow is Snapshot-Isolated December 23, 2024 We are apparently continuing our series of posts borne from thinking about Amazon DSQL. Today we are talking about skew. Amy and Bill are two developers...
- Coupled Code is Cool December 30, 2024 Happy new year, nothing too deep this week because I am traveling. If you read NULL BITMAP this year you have my gratitude. Peace and love. One of the...
- Channel Sharding in Go January 6, 2025 It’s a common pattern in Go to fan out I/O-bound tasks to a bunch of worker Goroutines. We have some big batch of work that has to get done, and we dole it...
- A Trick That Doesn't Work and a Trick That Does January 13, 2025 Ancestry I came across a cool algorithm recently for being able to efficiently answer ancestor queries in a tree ("is x an ancestor of y"). The trick is to...
- A Review of Extensible Query Optimizers in Practice January 20, 2025 My roommate and I are in a war with UPS. I came home the other day to find she’d left this note on our front door: It would appear she also has some kind of...
- Trampolines for SQL January 27, 2025 It is CIDR time and that means there is a lot of out-there papers in the world of databases to look at. If you are not familiar, CIDR is the Conference on...
- Are Correctness Conditions Descriptive or Prescriptive? February 3, 2025 Please see the bottom of this issue for a programming note! Correctness conditions constrain the sequences of events that are allowed to occur in a system...
- Why Feedback Control Interests Me+Discussion Group February 10, 2025 I got enough positive interest in some variety of book club that I would like to move forward with that. I want to discuss Feedback Control for Computer...
- What if SQL Was Informed by LSMs? February 17, 2025 Programming Note: Feedback Control Study Group I'm hosting what I am calling a "study group" about feedback control, loosely backed by Feedback Control for...
- More Blind Writes and Merge Operators February 24, 2025 Programming Note There is one week left to email me (firstname . lastname at gmail.com, or reply to this email) your thoughts on the first two chapters of...
- Chapters 1 & 2 of Feedback Control March 3, 2025 Hello! I hope you all had a good weekend. This is the first "study group" issue where I will share thoughts on the first two chapters of Feedback Control for...
- Philosophy and Methodology of Experiments March 10, 2025 Sometimes you have to do an experiment. This is rote, manual work that is chiefly concerned with data collection. I'm mostly talking about performance...
- Chapter 3 & 4 of Feedback Control March 17, 2025 We are reading Feedback Control for Computer Systems: Introducing Control Theory to Enterprise Programmers by Philipp K. Janert. For discussion, please see...
- It's Time to Stop Building KV Databases March 24, 2025 I'm so sick of Key-Value. The most unopinionated, uninspired data model that is a pain to use for anything. They're very popular! Among database vendors. Or,...
- Key(anti)chains March 31, 2025 This week I was supposed to write about chapters 5 and 6 of the feedback control book but I had a busy week and so wanted to talk about something a bit more...
- Feedback Ch 5 6 April 7, 2025 I am tired. I have been travelling and sick and oncall for the past couple weeks. I hope you're all having a good time. I have been thinking lately about the...
- Parsing is Search April 14, 2025 Something I didn't appreciate for a while (despite the term backtracking being prevalent in both cases) was the extent to which parsing is a search problem....
- Propositional Parlor Puzzle April 21, 2025 I've recently been playing Blue Prince, which is a great time if you are a fan of puzzle games like Return of the Obra Dinn or Outer Wilds and also a fan of...
2024 53
- Automating the Blue Prince Parlor Puzzle April 28, 2025 This is a continuation of last week's post. Please read that one first! In that post, we built an engine that could take puzzles of the following form: blue:...
- How To Understand That Jepsen Report May 5, 2025 There is a new Jepsen report which, as always, is an entertaining read and gives some insight into the way things might be broken in subtle ways. I learned...
- Solving Rubik's Cubes with Computers August 5, 2024 The first place I got into programming was making games. You can probably dig up some games I made long ago if you try hard enough (do not). In high school,...
- Some Books I Like // One Year of NULL BITMAP August 12, 2024 This is the 52nd NULL BITMAP, which means I have been doing this for a whole year! I skipped one week before I decided that this was going to be a weekly...
- The Closed-Loop Benchmark Trap August 19, 2024 Let's make a little mock database. It won't actually do anything but pretend to handle requests. I've had cause at work lately to write some Go so we're...
- Languages Without Abstraction August 26, 2024 Implementing something like a compiler, there is the understanding that we want different representations of a program for different purposes. This is why we...
- SQL's Grammar Ambiguity September 2, 2024 I was going to write a longer, more involved post this week, but I wound up getting Covid and didn't have it in me to work through all the stuff I had to for...
- Measuring Throughput September 9, 2024 Note: I'm trying out enabling comments. Behave! I reserve the right to disable them again for any reason including "the very idea of someone commenting made...
- Benchmarks That Aren't Your Friends September 16, 2024 We’ve now talked twice about an important dimension of a benchmark: the openness of the loop. While there’s more subtlety to it, if what you take away is:...
- The Two Machines September 23, 2024 There's a joke in my friend circle that asks "is it a database?" A startup, a program, a syscall, a person good with numbers, a person with a good memory....
- Integrity Constraints and the Relational Derivative September 30, 2024 In a SQL database, you can set up a foreign key with REFERENCES: nullbitmap=# CREATE TABLE ab (a INT PRIMARY KEY, b INT); CREATE TABLE nullbitmap=# INSERT...
- The Relational Derivative Pt. 2: Groups are Good October 7, 2024 Last week we talked about the notion of the relational derivative and its application to enforcing integrity constraints in databases. The relational...
- Linearity in Query Processing October 14, 2024 I saw a fun post this week about interpreting colours as vectors and the way you can exploit that interpretation to nicely represent certain operations you...
- Pushing Values to Zero October 21, 2024 There is a popular presentation of the exponential distribution that goes through the geometric distribution. The geometric distribution arises from flipping...
- Adventures in Probability October 28, 2024 I hope everyone had a good weekend. I went on a hike. It was great. Statistics One of my great school regrets, next to “taking three years of business...
- How Many Grains of Sand are in a Pile November 4, 2024 “This code’s no good,” says Pittsford, pointing at the screen: def update_and_get_balance(account, amount): database.debit(account, amount) return...
- The CVM Algorithm November 11, 2024 Everything you need to know about query planning can be understood from this query: SELECT * FROM xy WHERE y = 3 ORDER BY x Imagine we have two indexes, one...
- The Prequel to SQL is SEQUEL November 18, 2024 Meta note: follow me on Bluesky if you are so inclined. I've been going through some historical stuff lately. Been on a history kick. We went to see the...
- Fine! I'll Play With Skiplists November 25, 2024 Follow me on Bluesky! A Log-Structured Merge tree, or LSM, is a popular data structure for storage engines. It’s what is used by RocksDB, which is sort of...
- Thoughts on DuckDB's Grammar Patching Thing December 2, 2024 It is the job of modern programming languages to be amenable to abstractions. It should be easy for users to take a little bundle of functionality and reuse...
- What are the Magical Clocks for? December 9, 2024 At Re:Invent last week, AWS announced DSQL, their new serverless SQL database. As a fan of distributed SQL databases I have been enjoying reading about the...
- Why are Things Associative? December 16, 2024 The big three algebraic properties that show up in the distributed systems literature are associative, commutativity, and idempotency (EYE-dem-po-ten-see)....
- So You Want to Generate SQL Queries (me too) March 18, 2024 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...
- When Compositionality Fails March 25, 2024 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...
- A Sniff Test for Some Query Optimizers April 1, 2024 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...
- My First Distributed System April 8, 2024 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...
- The Geometry of SQL April 15, 2024 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...
- Heath's Theorem April 22, 2024 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...
- Not all Graphs are Trees April 29, 2024 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...
- The Official NULL BITMAP Glossary: Graph Theory Edition May 6, 2024 Last week a post of mine made it to God’s favourite website and one thing I was struck by was how many people disagreed about basic graph theory terminology....
- A Card Counting Trick May 13, 2024 I used to call this thing a “game” but my friend Kevin (who is not the same Kevin as last week but who is also a mathematician) kept telling me it’s really...
- NULL BITMAP Builds a Database #1: The Log is Literally the Database May 20, 2024 It is time to end the tyranny of people becoming interested in database implementation and building a BTree. Let us turn to the succor of immutable storage....
- Avoiding Cross Products with the Query Graph May 27, 2024 To compute the join of two relations, we find all pairs of rows their rows which have the same value for any columns with the same name. This is sometimes...
- TPC-See? June 3, 2024 One thing about concurrency control (“isolation”) in a transactional database is that it incurs costs, and there’s broadly two kinds of such costs. The first...
- NULL BITMAP Builds a Database #2: Enter the Memtable June 10, 2024 I didn't realize how hard it would be to bin-pack episodes of this thing into the roughly ~750 word chunks that I try to keep issues of this newsletter at....
- In Codd we Trust (or not) June 17, 2024 Get in loser, we’re doing another Codd philosophizing session. Codd’s paper introducing the relational model opens up like so: Future users of large data...
- Physical Properties #4 June 24, 2024 Previous parts of this series: Physical Properties #1 Physical Properties #2 Physical Properties #3 Relational query planning makes a distinction between...
- To Understand Correctness, You Must First Understand Incorrectness July 1, 2024 Recently I was in a Discord channel where someone wrote something akin to “I have a question about linearizability” which had an attached thread with 80...
- Deriving Functional Dependencies for Selections July 8, 2024 Over the last two weeks you were babysat by the pre-scheduling feature of Buttondown, since I was away in Japan without my laptop. Here's me in Japan: I had...
- Multiple Returns in SQL July 15, 2024 Podcast Appearance I was on the Thinking About Computers podcast recently! We had a fun chat on the topic of writing technical content and research....
- A Query Planning Guideline July 22, 2024 A number of readers last week reached out to direct my attention to What if a SQL Statement Returned a Database which is a much more thorough and well-...
- What do we want? Negation! When do we want it? Not later! July 29, 2024 Hello I am traveling this weekend! I am home in Ontario. I wanted to share this picture I took of this guy feeding a bear. Bear eating an object out of a...
- Databases are not Compilers October 30, 2023 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(*)...
- SQL Scoping is Surprisingly Subtle and Semantic November 6, 2023 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...
- A Left-to-Right Mental Model for Datalog November 13, 2023 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...
- Independence and The Futility of Cardinality Estimation November 20, 2023 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...
- Simplifying Expressions Bottom-Up November 27, 2023 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...
- The Little Planner Chapter 4: A Pushdown Party December 4, 2023 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...
- Thinking about Closure and LSMs December 11, 2023 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...
- Tiering vs. Leveling December 18, 2023 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...
- Should you read about "Database Theory?" December 25, 2023 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....
- Reification and Exchange January 1, 2024 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...
- Certificates and Duality January 8, 2024 I wanna talk about optimization. Not query optimization, or program optimization, today, but the other kind. Mathematical optimization. Like when your high...
2023 19
- Why SQL is Unkillable January 15, 2024 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...
- Testing Query Planners January 22, 2024 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...
- Physical Properties #1 January 29, 2024 I wanna talk about relational algebra. Specifically, the things relational algebra is not concerned with, but obviously matter. Things like: ordering of a...
- Physical Properties #2 February 5, 2024 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 #3 February 12, 2024 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...
- The Three Places for Data in an LSM February 19, 2024 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....
- Some of My Favourite Query Planning Papers February 26, 2024 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...
- A Very Basic Decorrelator March 4, 2024 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,...
- CAP is Good, Actually March 11, 2024 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...
- The Halloween Problem August 14, 2023 What if you had an isolation anomaly with yourself? If you're receiving this as an email, thank you for entrusting me with your email address, I know that's...
- Hard and Soft Statistics August 28, 2023 One lens I've found satisfying for "what is a query planner" is that it's a tool for "approximating domain knowledge." By that I mean, someone who knows...
- The Problem with Declarativity September 4, 2023 IN or OR There was a very nice blog post from OtterTune [1] recently, digging into some of the quirks of the way Postgres executes a particular query: Query...
- VLDB Reading List #1: TUM Edition September 11, 2023 VLDB just happened! And I have been going through some of the papers that caught my eye. As it turns out, this week is TUM week. What Modern NVMe Storage Can...
- Unity and VLDB Reading List #2 September 18, 2023 Normies Learn Software Licensing If you're a software person and at all plugged in to the world of video games, you might have watched in horror as Unity...
- Internal Affairs September 25, 2023 There is a trick called string interning that is well known to compiler authors, and sometimes shows up in other places as well. It's used to change the...
- Why Are Query Plans Trees? October 2, 2023 Looking at just about any database's EXPLAIN output will reveal that generally, queries get compiled into tree-shaped plans, rather than general cyclic...
- Representing Columns in Query Optimizers October 9, 2023 Query optimizers must have a way to internally represent their plans. This is query planning's version of an "intermediate representation," or IR. There's a...
- Databases Have a Lot of Data October 16, 2023 A recurring theme in the ongoing coverage of Sam Bankman-Fried's trial has been his apparent recklessness. One particularly popular anecdote being his...
- The Case of a Curious SQL Query October 23, 2023 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...