Are Correctness Conditions Descriptive or Prescriptive?
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...
Trampolines for SQL
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...
A Review of Extensible Query Optimizers in Practice
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...
A Trick That Doesn't Work and a Trick That Does
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...
Channel Sharding in Go
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...
Coupled Code is Cool
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...
Git Workflow is Snapshot-Isolated
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...
Why are Things Associative?
The big three algebraic properties that show up in the distributed systems literature are associative, commutativity, and idempotency (EYE-dem-po-ten-see)....
What are the Magical Clocks for?
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...
Thoughts on DuckDB's Grammar Patching Thing
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...
Fine! I'll Play With Skiplists
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...
The Prequel to SQL is SEQUEL
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...
The CVM Algorithm
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...
How Many Grains of Sand are in a Pile
“This code’s no good,” says Pittsford, pointing at the screen: def update_and_get_balance(account, amount): database.debit(account, amount) return...
Adventures in Probability
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...
Pushing Values to Zero
There is a popular presentation of the exponential distribution that goes through the geometric distribution. The geometric distribution arises from flipping...
Linearity in Query Processing
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...
The Relational Derivative Pt. 2: Groups are Good
Last week we talked about the notion of the relational derivative and its application to enforcing integrity constraints in databases. The relational...
Integrity Constraints and the Relational Derivative
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 Two Machines
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....
