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 am also active on Bluesky !
Programming note; this is the 150th issue of NULL BITMAP, and NULL BITMAP will be going on a hiatus for a while, maybe just for the Summer, maybe indefinitely. I think I need a bit of a break from it and I don't think the weekly cadence is serving me like it once did. I have been poking around the Jujutsu repo recently, and I was very pleased to realize that this thing has a whole query language…
Much like everyone else who wants to engage as little as possible with "here are some effective threats to make the computer do what you want" while still learning about exciting new computer things, I have been learning how to use Jujutsu . I recently had my epiphany insight where it all clicked and I understood the mental model (which I will not share, because of theory ). Something this has me…
I might have mentioned before that I've been slowly working through the Simple tutorial for building a Sea of Nodes compiler. A lot of it is still sort of going over my head but I've learned a couple of interesting things in the process of working through it that I think I can bring back to a query planning context. One thing I learned from it is that my understanding of Hash Consing was a bit…
LangChain recently posted about a database they built. I liked the post quite a bit, I thought it was pretty well written and did a really good job of explaining their architecture. It highlighted for me some of the interesting database challenges and workloads that are consequences of AI. This is an "observability database," which sits sort of outside the traditional OLTP/OLAP dichotomy, but…
I have been tinkering with a little tactics game not so different from Fire Emblem. One thing I'm doing that I think is somewhat novel in the space is involving a technique I learned from studying Timely Dataflow : partially ordered costs for pathfinding. In Timely, it's used to represent complex versions of time that allow for multitemporal processing . I've written about this before but back…
I have been tinkering with non-database stuff recently and I don't really have any of it in a place to share something fun about. So in the interim, here is a small collection of some tricks I like a lot. I like bitwise tricks a lot. Here's a couple that are not particularly useful, but are fun and cool. If you like these, you should read Hacker's Delight . 1. Average of two numbers The problem…
I had a picnic this weekend and at it I gave Phil a pen plot that I had been meaning to for a while: I want to explain it here because I think it's cool! This was drawn with a pen plotter, which is a kind of robotic arm that you can place a pen in, and program to draw very precisely. The result is that you can get crisper lines, that were drawn with a pen instead of inkjet (which also means you…
I have long thought of the hash join/merge join duopoly as reflective of the fundamental truth that basically all data-processing related algorithms are based on either hashing or sorting. Yes, we also have nested loop join, but that's sort of just hash join in disguise. Aggregation? Your options are sorting and grouping, or hash bucketing. Deduplication? Same deal. Union? Intersection?…
I've been reflecting a bit on my philosophy of learning stuff. How I like to think about things (and maybe how you like to think about things, if you like to read this newsletter). I make a lot of observations of the form " X is Y " which tend to get understood sometimes as being reductive, and missing important aspects of both concepts. Which is strange to me because I think it seems fairly clear…
I used to have this thought that optimizations in compilers and databases were a bit of a bandaid to badly-written code or something. I think this is not a correct mental model, though. I've also been trying to learn more about compilers recently, just because I have query planning problems that I feel like must have already been solved by the compiler world. So here's some musing. Languages like…
Something I didn't understand for a while is that the process of turning row-oriented data into column-oriented data isn't a totally bespoke, foreign concept in the realm of databases. It's still of the relational abstraction. Or can be. As an example, say we have this data: data = [ { "name" : "Smudge" , "colour" : "black" }, { "name" : "Sissel" , "colour" : "grey" }, { "name" : "Hamlet" ,…
We talk here sometimes about how to test SQL dialects with tools like TLP and PQS . One really nice property of those tools is that they let you treat the database like a blackbox. I'm tinkering with a little SQL planner to mess around with ideas and one feature I added very early was an explicit optimization fence operator that simply blocks any optimizations: In a query like this: SELECT * FROM…
I love sampling algorithms. Here's the sampling algorithm that I find most magical. We want to generate a subset of {1, 2, ..., n} of size k . def floyd ( n , k ): s = set () for i in range ( n - k + 1 , n + 1 ): t = random . randint ( 1 , i ) if t in s : s . add ( i ) else : s . add ( t ) return s I learned about this algorithm the canonical way all good algorithm lore is imparted; one of my old…
Every time I have ever explained the Boyer-Moore majority element algorithm to someone, people have reliably found it very charming. So now I'm going to explain it to you. The problem is this: we have an array of elements which we are told possesses a majority element . That is, an element which occurs more than half the time. We would like to figure out what that element is. There's couple…
We love generative testing in the world of query languages, because languages in general are in a lot of ways, too complex to test by hand. There's an exponential number of combinations of features that could be involved in any given query. Database query optimizers do a lot of work to detect when those features are used together in ways that permit better execution. This is great, and important,…
I've liked Cryptic Crosswords...somewhat. In the past. They're a bit tricky for me and I haven't really put in the time to be comfortable enough to have fun solving them. Anyway, the Wordle guy has a new website where he aims to teach people how to solve Cryptics. If you're not familiar, Cryptic Crosswords follow a very particular format for their clues. Let's take one of the Parseword examples:…
Last week we simulated a queueing algorithm. Behind the scenes, I did this by writing a Go program and placing sleeps to simulate processing. This meant that running a simulation took a while. I ran each one for about a minute, and adding more simulations where I varied parameters took longer and longer. How might we run simulations that don't use the real computer clock? One way to model such a…
I read a great post this week from Marc Brooker: SFQ: Simple, Stateless, Stochastic Fairness . In it, Marc does a great job of explaining a cute little algorithm for isolating different customers from each other in a multitenant system. You should go read that post first. I was curious to improve my intuition on how it is that this algorithm works so I wrote some simulations to see how it behaves…
We talked a couple issues ago about the application of Linearity of Expectation to building intuition about Copysets , and the ways that we're both constrained and freed by the laws of probability. Evan recently pointed out a cool paper and writeup to me that can be understood in a similar way. Here's the problem as he described it to me: This is a really basic idea: generate unique IDs, in this…
My friend taught me a really funny parsing algorithm this week and sent me Operator precedence by textual substitution . I love really funny parsing algorithms, so I wanted to try to figure out and explain why this algorithm works: An ingenious idea used in the first FORTRAN compiler was to surround binary operators with peculiar-looking parentheses: + and - were replaced by )))+((( and )))-((( *…
That expectation is linear is one of my favourite facts. I got a first taste of this when I was doing an internship at an unnamed trading firm. Some guy was teaching me the basics of trading and showing me how traders (of which I was not one) were expected to have heuristics that would allow them to make snap judgments about things like expectation. As an example, he asked me, in more words, what…
I was going through the list of CIDR papers this year and looking for ones that were relevant to my interests. If you're not familiar with CIDR as an institution, it's basically the "short, kind of kooky" database papers conference. You're more likely to find things that are a little looser, a little more speculative, a little more off the wall, and a little more self-contained. I enjoyed On the…
That's right, we're back to the world of databases. Not because I haven't been screwing around with my dinky little compiler but because I was starting to get embarrassed about how little I've been writing about databases which is ostensibly what you signed up for. This week I thought we'd revisit an old classic: Online, Asynchronous Schema Change in F1 . F1 is the original name for the SQL layer…
Last week I talked about my forays into Compiler Construction (1996). This week, I have worked through more of the book and I'm going to share some of my explorations on Wirth's approach to constant folding (and some other optimizations). Part of the guiding principle of how this book wants you to design a compiler is that we should act locally to the extent that we can. No materializing syntax…
Something I believe wholeheartedly is that writing simple little programs is good, and writing the same simple little programs many times is even better. I've been reading Niklaus Wirth's Compiler Construction recently and I think Wirth's whole deal really embodies this. Wirth is notable for his belief that simple methods of implementing ideas are better than complex ones. This sounds sort of like…
I recently came across a cute game called https://enclose.horse. In this game, there is a horse in the middle of a field and a bunch of rivers surrounding it. You have to "enclose" the horse by cutting off its access to the boundaries of the map using a limited set of walls. The game is to create the largest possible space you can under those constraints. It's harder to explain in words than if…
This is the last NULL BITMAP of the year. If you read these with any regularity, sincerely, thanks for spending time with me every week. Reflecting on the year, I have been a bit down about the future of programming culturally, with the advent of LLMs it feels like people are telling me that being interested in how things work and how best to think about things is a waste of time. That "no, no,…
I am busy with holiday stuff so this post is a little bit half-baked. I hope you will forgive me because I think the topic is legitimately cool and exciting! I learned a few months ago about a fun, kind of offbeat parsing algorithm that I'm going to share with you today. I learned about this from Parsing Techniques: A Practical Guide , which if you're interested in goofy parsing algorithms I…
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 * FROM ab WHERE a = 7 AND b = 100 We can: Not decompose the filter at all, and scan our base data applying the predicate a = 7 AND b = 100 , push down the a = 7 filter and translate the scan over the primary index into a scan on a secondary…
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 quite often in everyday programming. Imagine we have a database and a relation with two columns, a and b , along with two indexes: one on a , and one on b . We can write some code to simulate this. First, we can create a dataset of a s and b s:…