In this post, Andy Warfield explains how databases like DuckDB are enabling a new way to build with data, why they matter right now, and how they complement the work we’ve been doing in S3 (e.g., S3 Files, S3 Tables, S3 Vectors). And most importantly, why DuckLabs, the team behind DuckDB, is joining AWS
We recently switched to version 7 (v7) uuid primary keys and saw significantly faster inserts for some tables. The databases were running Postgres 18.4 and mostly used v1 with some v4 uuid values for primary keys. Changing the column default involved running a single alter table command, but did require an exclusive lock on the table, blocking everything including selects. To solve that, we used a short lock timeout and lots of retries. The biggest speedup was 23x faster average execution time for a multi-row insert query called 12,000 times per minute on a table with billions of rows. This September and October I'll be in Austin, TX and NYC, check my Book page for upcoming appearances. The system uses UUID primary keys throughout. I typically recommend starting with bigint and sequences over UUID v4 primary keys , although here uuid v1 was used. Insert performance is not as bad for v1 compared with v4. Still though, v7 brings better performance than both for inserts and can also result in smaller indexes with fewer page splits meaning less CPU and IO. What drives bad performance for v4 and to a lesser extent v1? Let’s do a quick refresher. As new table rows are inserted and a primary key is defined, primary key values are maintained in sorted order in a b-tree index. Just like table rows, index entries in Postgres are stored in fixed size 8kb pages. Postgres needs to know in which page to place the new index entry. For sorted order, the first bytes of new uuid values are compared. For v4 given new values are very random and not monotonically increasing (they lack “monotonicity”), values can be earlier or later, meaning they’re unlikely to be placed into the same recently accessed page. This is bad for caching! When new values are monotonically increasing, the recently accessed page is “hot” in the Postgres buffer cache (in memory copy of the on-disk page). When Postgres is not able to use the hot index page for the newly inserted value, that page could be outside the buffer cache, not in the OS cache, and ultimately result in a much slower disk read which increases latency. Besides the worse insert performance, since v4 values are scattered to more pages, this means there are more “page splits” when new inserts are attempted in full pages. Page splits cause more latency from increase WAL and IO. We experimented and benchmarked with v1, v4, and v7 uuid formats and we leveraged the research and write-ups from external sources like the ones below. Benchmarks are great, but what kind of real world results did we see? We decided to make this the new default unless v4 was needed for more randomness. After all qualified tables were changed, I began going through insert queries for each changed table. For many of the tables, there wasn’t an obvious change. However, for a handful we saw an immediate and significant improvement. I picked 5 with speedups of 6x, 8x, 9x, 20x, and 23x. The PgAnalyze graphs for the 23x, 9x, and 6x queries are shown below. Showing PgAnalyze insert query graphs for tables A, B, C: Table A - 23x reduction. 0.7ms to 0.03ms, 12000 calls/min Table B - 9x reduction. 0.6ms to 0.07ms, 2000 calls/min Table C - 6x reduction. 0.50ms to 0.08ms, 9500 calls/min Now that we’ve seen the results, let’s talk about how this was done and the challenges. The UUID values came from various sources: We replaced most of these with the function in Postgres 18. To do that, we needed to run a single statement per table. The statement ran fast, so no problem, right? One wrinkle we found was that modifying the column default while fast, required an lock. This lock type conflicts with every read and write operation including regular statements. For our highest queried tables, they’re queried constantly, so this was a problem. There was almost never a “window” to perform this operation, and we didn’t want to take downtime for this switch. While heavily queried tables were a challenge, infrequently queried tables did not pose a problem for this alter table statement at all. For those, we could use our migrations framework (Active Record in Ruby on Rails) and perform the using a regular old migration. For those, we did add some safeguards, by creating an explicit transaction and using to control timeout values. We’d set short timeouts for the to give up quickly if it didn’t work or ran too long. For the higher activity tables, we’d need some retries. We’d use a manual psql session: The would commit if it grabbed the lock within 50ms, or we’d get an error that the was reached. The benefit of the manual approach was we could retry until successful and backfill a Rails migration to keep everything in sync. A more sophisticated solution might have automated retries within Ruby. However, for our most heavily queried tables, we wanted even more control over the retries. How did we do that? Sometimes one or two retries would do the job. Great, we’d move on. However, for our most heavily queried table that didn’t work. What ended up working was using the same strategy of retries, but just adding more sophistication with looping and backoffs. Claude helped me cook up the PL/pgSQL looping retry function below, I did some testing and was ready to try it. It has these features: By using the function above, we were able to find a small window to perform the after several dozen quick retries! In cases where even many retries won’t work, and we don’t want downtime, we may be left with needing to actively monitor lock holder queries and to cancel them (assuming that’s ok). Thanks to Ants Aasma from the community PostgreSQL Slack for this idea. We didn’t end up needing to do this, but here was my prep for this. It’s still useful to review lock holder queries. First we’d inspect live queries: And identify queries holding locks: If we find them, we could cancel them to create a window to run our . That could mean bad user experience so you’d need to figure that out for your database. We’d likely want to stack up our operation to occur immediately after. Fortunately we didn’t end up needing to do this, but I’d be interested to hear the stories from others with heavily queried databases. Since uuid v7 values use a timestamp in their first bits, this timestamp can be easily decoded. This can be viewed as “leaking” or exposing the creation time of the record via that timestamp, which could be a downside for your database. You’ll have to decide that. v4 UUIDs do not expose the creation time. We found some significant speedups for insert queries after switching to primary keys, for a relatively low effort change. A nice ROI. The only wrinkle was the exclusive lock required, but we solved that with short lock related timeouts and many retries. Although this didn’t benefit 100% of our tables, the gains for some were significant and uuid v7 has become our new default choice for uuid primary keys. Thanks to the Postgres core team for creating this new capability within Postgres. The availability in core made it possible to adopt on AWS RDS which supports a limited amount of extensions. Thanks for reading, and until next time. How Sequential UUIDv7 Boosts Ingestion Performance Simplicity and power of UUID v7 PostgreSQL UUID Performance: Benchmarking Random (v4) and Time-based (v7) UUIDs The function from the module The function added in Postgres 13 that generates v4 UUIDs natively UUID v4 values sent by a client application, which meant the column default function was not used Try up to 50 times (max attempts is configurable) Add a pause in between retries, with a jittered backoff of 50-250ms
I have been probably obsessed with two things in the last few years: Nix as a tool to explore innovative ideas that require the capability to rebuild the world and replacing ELF with SQLite as an executable format. You might have noticed that these two ideas are well suited to each other. I explored the idea during my PhD thesis but found feedback from others unmotivating. Radical ideas are hard to sell, as you are working against the inertia of the established solution. One of the end results of that exploration was sqlelf , a tool that lets you explore an ELF file declaratively using SQL. 1 instead of fiddling with and . It was remarkably simple by leveraging virtual tables over the ELF: however I found it to be a refreshing improvement to explore the ELF file format. I knew however that there is still something much bigger to be done. I never let the idea go and with the recent improvements with LLMs, I find it compelling to revisit these ideas to explore further. Specifically, can we replace ELF with SQLite as an executable format? 🤔 Not “a database that describes an executable”, but the actual file you and run. I developed a pretty fleshed out prototype. It is called SELF , the Structured Executable & Linkable Format , because I am unoriginal. It is on GitHub if you are interested. I’m surprised about all the interesting things that fall out of this idea. Working through my PhD, I realized something that bugged me. ELF is already a database. It just implements many database primitives by hand, along with a surprising number of data structures for performance, like a bloom filter for symbol lookup. If you ever have to analyze or parse ELF, the kernel, , binutils, LIEF, goblin, , you are re-implementing the same parser over and over again. Every producer re-implements the same serializer. The format itself is incredibly terse, designed for a world where disk space and network bandwidth was at an extreme premium. Modifying the format is hard, you often have to zero out sections and add new ones since it is packed so tightly. There is also no self-describing schema. ELF itself is a very generic format that supports sections of data that by convention are interpreted in specific ways but the format does not enforce it. SQLite is the counter-example. They are a self-describing format that is extremely stable. It is designed to be extended to support new features without breaking existing consumers and supporting a wide range of queries performantly. If we were to replace ELF with SQLite, what would fall out and can all of the necessary information be represented in a SQLite database? The answer is yes, and it is surprisingly simple. A SELF file needs two tables to run: is the ELF header as key/value pairs and is the load image, one row per program header with the bytes in a : A single table for the symbol table replaces many of the ELF sections and the index. It is a single table with a single index: Our capability to include an index is equivalent to and in ELF, but it is a proper b-tree index maintained by SQLite instead of a hand-rolled bloom filter. 2 Surprisingly a lot more falls out as well: is gone, because is and SQLite already interns strings, symbol versioning is a column, not the / contraption and there is no need for a table. Other tables exist as well for metadata which exist for tooling: , , . Delete them and the program still runs, which means is a transaction: All the tools that operate on ELF files for reading, reduce to queries over the database. Any tool that modifies an ELF file, like , can operate on the database within a transaction rather than performing fragile offset surgery: is a and . is an . Any information missing from the schema can be easily exposed via a view. For example, is a query over the table, which is a join of the table with the table to find the sonames of the libraries needed by the program. SQLite reserves a 4-byte at byte offset 68 of its header, for exactly this purpose. We stamp it , so an ordinary SQLite database never matches: We can now leverage binfmt_misc , the subsystem that allows you to invoke any binary as if it were native. We need only to register the magic to trigger on and an interpreter that will invoke our new file format. On NixOS the registration is a few lines matching the SQLite magic at offset 0 and at 68: For now, I have a small tool that converts an ELF file into a SELF file. It is a simple hook you can opt into per package on NixOS. The tool reads the ELF, extracts the program headers and symbol table, and writes them into the SQLite database. We could look at extending or to emit SELF directly, but for now this is a simple way to explore the idea. is the interpreter. It is a small C program linked against . Its implementation is remarkably similar to that of but it fetches the program headers and symbol table from the database instead of reading them from the ELF file. It maps the loadable segments into memory, relocates them, and jumps to the entry point. Note has to stay an ELF file. An interpreter that also matches the registration recurses straight into . Running a static program was quick and easy but boring and unimaginative. The interesting part is dynamic linking, which is where the database shines. I explored two different ways to do dynamic linking. The first is to keep and just replace the lookup with a SQL query via rtld-audit interface, to quickly iterate on the design. The second is to replace entirely with a new dynamic linker that does the entire lookup and binding in SQL. glibc’s rtld-audit interface lets an audit library intercept every shared object lookup ( ) before any filesystem search happens, included. The audit library can then answer the question “which library satisfies this symbol?” with a SQL query instead of walking the and . Stock maps and relocates it, so the full gamut of glibc features work: lazy PLT, IFUNCs, TLS and symbol versioning, while library storage are rows and library lookups are queries. I was curious what a fully SQL dynamic linker would look like, so I prototyped one. It is called and it is a small C program that implements the dynamic linker entirely in SQL. It is a proof-of-concept, but it works. It maps every object’s segments, publishes their exports, and for each relocation patches the GOT and jumps to the start. The two things that often matter when replacing a well-established format are size and latency. How much bigger is a SELF file than an ELF file, and how much slower is it to run? Size. A SELF file carries SQLite’s b-tree overhead and lands at roughly double the ELF. Similar to ELF binaries, most of that is recoverable, because the overhead is mostly the optional tables for debugging and tooling. Stripping them and deleting them is a transaction. A stripped SELF is 1,794,048 B against the ELF’s 1,768,632 B, that is within 1% . We will see though that there are interesting ways to amortise the overhead even more which I found very unique and interesting. Latency. I benchmarked various binaries from a 15 KiB to a 42 MiB linking 47 libraries: There is a fixed ~5 ms to open SQLite and start the interpreter, plus a copy proportional to the image. That copy is worse than it looks, because the b-tree pages are not mapped into memory. Two processes running the same SELF binary do not share text pages the way a normally- ‘d ELF does, because the bytes are copied out of the b-tree rather than mapped. 3 A SQLite database though need not merely be a single executable. It can be a closure , a single file that contains a program and all of its transitive dependencies. The output of a program is ambiguous: it only lists the sonames of the libraries it needs, not the specific files that satisfy those needs. Nix improves upon this by explicitly resolving every edge to a specific store path via the use of . 4 We can do the same in SELF by storing the resolved path of each edge in the database: packs a binary and its transitive dependencies into one database with those edges filled in. Shared library resolution stops being a guess and becomes a foreign key and becomes a 🤯: This single database is a closure of the executable and its five libraries: six objects, segment bytes and all, in one 4.8 MiB file. There is no soname ambiguity inside a closure, because a closure by construction contains exactly one provider per edge. I hope you’ve been with me so far, because this is where it gets really interesting. We can go even further and pack multiple closures into a single database. I pointed at every ELF binary on this system’s : 723 executables, which pull in 400 distinct shared libraries. 1,123 objects, 346,386 symbols, 3,808 dependency edges, all as one SQLite file . Turns out when you do that, the database is much smaller than you would expect. 611.9 MiB of database against 644.4 MiB of ELF files. The whole userland, as one queryable file, is smaller than the files it came from. The b-tree cost that doubled a single amortises to nearly nothing across 1,123 objects and is roughly 6% over the actual program bytes. The libraries and closure are shared across the executables very similar to how Nix might share them across multiple closures, if the store-path was the same. If every root shipped its own private closure (i.e. the AppImage model), the same 723 programs would come to 5.53 GiB but the deduplication of libraries and symbols falls out naturally from the database schema. Many common idioms we use in ELF immediately fall out of the database. For example, is a row in a table rather than an environment variable. The table is a list of objects to map last, so their exports win. This means that turning on and off is a transaction. We were able to accomplish an atomic across a whole userland in one file, “interpose a tracing everywhere, then ” is a single transaction. 😈 The format is done and round-trips between ELF and SELF losslessly. The tooling is done and can query, modify, and pack closures. Lookup through SQL works on unmodified glibc programs perfectly and the native-SQL loader works enough to explore it as a possibility for ideas. The whole thing is at fzakaria/selfdb . boots a NixOS VM where is a SQLite database. 🙌 Nix lets us explore radical ideas like this. We can rebuild the world down to the Linux kernel if needed. We need not be constrained by the existing decisions and constraints of the past. We can explore new ideas and see what falls out. I hope you find this idea as interesting as I do. I wrote a paper, arXiv:2405.03883 , that I failed to get published and a follow-up post on querying with it . ↩ is a bloom filter plus bucket chains, laid out so can reject a miss without touching the chain during symbol discovery. ↩ You might notice that (274 KiB, 27 libraries) starts slower than ELF (4.6 MiB, 5 libraries). That is doing work proportional to the number of objects rather than the number of bytes, which I have complained about before . ↩ I have written about on Nix before such as making it redundant or speeding it up . ↩ I wrote a paper, arXiv:2405.03883 , that I failed to get published and a follow-up post on querying with it . ↩ is a bloom filter plus bucket chains, laid out so can reject a miss without touching the chain during symbol discovery. ↩ You might notice that (274 KiB, 27 libraries) starts slower than ELF (4.6 MiB, 5 libraries). That is doing work proportional to the number of objects rather than the number of bytes, which I have complained about before . ↩ I have written about on Nix before such as making it redundant or speeding it up . ↩
A while back, Claude Opus built a pretty ambitious compiler. I didn't set out to do anything nearly as ambitious as Anthropic's. They were targeting multiple CPU architectures and they wanted to be able to compile a bootable Linux kernel. (I'd actually forgotten about that project until I started posting some screenshots of the work below to social media and someone reminded me.) Last night, as I was getting ready for bed I was reaching for some project to support and tool use in Evener, our ~new agentic harness. I popped open the mobile UI on my phone and typed "Your job is to implement a standards-compliant ARM64 C compiler for macOS in Swift." Evener asked me a couple of questions. I clarified my intent a little bit: "I'm great with radical task decomposition. You should use recursive subagents to manage context and complexity.Should structure the project in whatever sane way you want. You should work fully autonomously And do not need to ask me questions." And then I set a goal: "Implement a standards-compliant C compiler in modern Swift. It should be able to build SQLIte and have SQLite pass all tests. You may decompose the project in any way you see fit. You should use subagents, including recursive subagents, to execute effectively." I don't know what I thought was going to happen. I watched long enough to make sure that it was going to start working. At about four in the morning I rolled over and looked at my phone and it was deep into debugging a malloc issue. I woke up at a little bit before seven and it was implementing variadic functions. Today I spent most of my day in meetings and so I didn't get a lot of time to watch it, but I would occasionally pull up a session and see it making little bits of progress. Occasionally it would dump out some assembler and then dump out 's version of the assembler to hunt for differences. I saw it trying to build the 274k amalgamation and segfaulting. I saw it writing little test scripts. I saw it get to the point of trying to do an and exploding. When I came up for air at about 8 30 p.m. I popped open Evener around my phone, and was incredibly disappointed. My loop had just...stopped. It's not supposed to do that. But that's exactly the failure that I was testing for. I started reading the recent parts of the log, to figure out which obvious problem had caused the failure. I was not expecting to see this: It stopped because it had compiled SQLite and was able to do an and a . It did exactly what I asked. It took Evener + GLM 5.2 about 21 hours to build a C compiler capable of compiling SQLite and passing a basic smoke test. This is the checkpoint: https://github.com/obra/toy-c-compiler/commit/456ddfa8912b5ba47b968773ecddcdca741f0df2 (I was initially worried that it had cheated by doing the obvious web searches, but discovered late in the day that I had accidentally broken the harness's web fetch tool. And so it wasn't able to cheat that way.) Checking now, it looks like it didn't even try , which makes me happy. There are a ton of missing features. It is not yet standards compliant, but I didn't properly set the goal to force that. I've just kicked off another to get it to run through compliance suites and fill in the missing features. I'll probably let it run for another day or two just to see what happens.
This is an external post of mine. Click here if you are not redirected.
SeaweedFS, FreeBSD and a rather deep rabbit hole At this point, reading my blog, you could be forgiven for thinking that I have become entirely about IBM midrange systems, COBOL and offline-first computing. That is still true, in a way. I genuinely enjoy those things. But I am still very much attracted to large, complex architectures, distributed systems, and the sort of infrastructure where several apparently innocent design decisions eventually turn into a whiteboard covered in arrows.
There is a machine called Productivity, and on this machine there is a knob and a button. The knob increases productivity, and the button is labeled "reset." My job was data entry at a non-profit. It was my first job in the US where I didn't have to lift heavy objects. My main task was entering collected donations into a database. The data source was email attachments, which came in various formats. Excel files, Word files, and some directly embedded in the email body. The database itself was FileMaker Pro. Every part of the process was wasteful. To receive the emails in the first place, I had to call the person who collected the donation, argue with them, and guide them through the process of emailing me the information. The donations were collected at events, and the data was often just handwritten on a note. Once I got the email, I would extract the content from the attachment and organize it into an Excel file. Then I would manually enter it into the FileMaker database, one row at a time. In a full workday, I could process no more than a dozen entries. So I decided to improve the process. I started from the end. Entering data into the database was error-prone. I had to enter the name, address, donation amount, and a plethora of other information into a single row of a database viewer, and I often put the wrong data in the wrong column. So instead, I created a form with validation. I built a standardized Excel file where the people collecting donations could enter data directly into the correct columns and send it to me. This turned out to be too much to ask. Several people didn't know how to use Excel, and it became a nightmare of technical support. Eventually, I switched to a formatted Word document. Annoying, but it worked. Lastly, I created a process. Every Monday, I would email everyone to remind them to send me their donations by Wednesday, so I would have plenty of time to enter them on schedule. The deadline was arbitrary, but it slowly hardened into policy. My system was a success. I was entering hundreds of donations every day. In terms of productivity, I had more than 10x'd my output, which I thought was a good thing, until I started getting noticed. What have you done for me lately? My productivity machine's knob had been dialed to 11. But I had also set the new standard for how much needed to get done in a day. So my manager hit the reset button. The dial went back to zero, but the expectation stayed exactly where it was. It's funny how that always happens. Increased output never turns into more free time. Instead, it becomes the new normal. Anything less looks like a drop in productivity. These days, with AI common in the workplace, every semi-technical manager has started building apps themselves instead of taking requests to the dev team. They get a rush from how much code they can produce, and they enjoy that high for a while. But they fail to see that the productivity gain only exists at the very beginning, before the app is actually in use. Once people start using it, you don't get to regenerate the app from scratch every time you want to add a feature. Instead, you have to add things slowly and carefully, without breaking what already works. All fields start green, but they brown eventually. When you get an extremely productive teammate, you start looking at the rest of the team as time-wasters. In fact, once you get used to what that teammate produces, you start treating it as the baseline and eventually you ask, "What have you done for me lately?" I was let go from that job in a little celebration, right after I'd trained my replacement. One morning, my manager simply announced that it had only ever been a summer job, and summer was ending. So my last day was set. I was too green to point out that this had never come up during hiring, and that I'd actually started well before summer began. They brought cake on my last day. What they failed to see was that my process was still very much manual. My replacement was let go when she couldn't manage more than a dozen entries a day. So much for productivity gains.
Tigris has a pretty advanced replication scheme for writes. What happens when you actually need to delete things? Turns out deleting things is hard in distributed systems. Especially when you have a geo-replicated active-active database like Tigris does. We can (and do) use tombstones to mark where data once was, but how do you let people undo an accidental delete? Tigris wants to turn storage inside out , so our implementation of soft deletion is by giving users the Recycle Bin for objects and buckets. Today we're going to dig into how this works, why it works, and what this gives you in terms of using object storage today. In Windows and macOS, the Recycle Bin (or Trash can) is a form of purgatory where deleted files wait for their storage to be deallocated by the user. This allows users to hit "delete" fearlessly because if they made a mistake they can just drag it back out and go on with life. This works great in your local filesystem because there's only one writer in one region. This kinda falls apart when you have multiple regions in your database and any one of them could be writing to it. How do you name things in the recycle bin? How do you handle the conflict of an update happening in one region before the deletion was fully replicated out from another region? This is the fun of distributed systems, which is the kind of problem space that Tigris lives in. One way to think about how the Recycle Bin works is that the file metadata gets moved there when the user hits delete. No data bytes move around on the disk, but the file doesn't show up in My Documents anymore. In a distributed systems context you can't just move the metadata around, you have to leave a tombstone behind to record where that metadata once was. This prevents other regions from being confused when actions happen really close to each other in time. At a high level, a soft-delete is when a DELETE action doesn't actually remove the data. When data is soft-deleted, it's still there but just not visible in the main usage flow. This lets you get the data back when a delete is made by accident. One of the interesting side effects of designing any API is that you end up leaking the internals of how your database works to your users. Many object storage systems were designed with overwriting or deleting data as one of the primary operations, and as such have had to bolt versioning onto the side. For the most part this does work; but once you get into advanced versioning schemes everything starts to fall apart. Tigris doesn't suffer from the same problems because we built immutability into the core from day one, and in immutable systems you have to append new data on the end instead of overwriting data. At the least, actually storing the data en masse is a boring problem. You put the data somewhere, maybe name it after the checksum of its contents, and then have a daemon make sure it's copied three places. That daemon also handles cases when drives go offline and new ones are added to make sure data is shuffled around the cluster. This is largely a solved problem with projects like Ceph, Longhorn, or other distributed storage systems. Some object storage systems like S3 expose platform internals to make soft deletion work. In S3 deleting an object creates a delete marker (tombstone). A delete marker is an explicit marker that the object is deleted and should not be returned in normal operation. Here's what that looks like in practice: I don't know how I feel about this flow. Based on reading between the lines in the delete marker documentation it really feels like this is a leaked internal implementation detail of how S3's eventually consistent database works instead of a full fledged feature of the storage system. If I had to choose between leaking internal database details in the API and implementing a higher level API for something complicated like soft deletion, I'd want to implement the higher level API. Let's rethink what soft deletes really are. What if they were like the Recycle Bin in Windows? Soft-deletes are external references to buckets or objects that live in a different namespace from normal buckets or objects. We implemented them as external references instead of tombstones because this is effectively moving object metadata to the recycle bin. Tombstones mark the data as not being there, but soft-delete markers are a copy of the data that was there. This makes it easy to put the object back in place if you deleted it by mistake. One way to think about objects and buckets is that they are garbage collection roots for points in the endless sea of data. Any data in the sea without a root anchoring it down is eligible to be deleted. Uploading multiple versions of an object with a forkable bucket creates multiple metadata entries at their different timestamped version numbers. You can then fork a bucket from any one of those timestamps to see what the bucket was like at that point: This would solve the soft-delete problem, but our existing database schema using FoundationDB requires us to enable forking and snapshots at bucket creation time. In essence, we need something that's halfway between what we have (each bucket being a globally mutable namespace) and the bucket forking land of every action being appending metadata onto the end. To do that, we basically implemented most of that appending metadata on the end trick but to a different place: the soft deletion corner. When you enable soft-deletion and delete an object, its metadata gets moved to the trashcan so you can pluck it back into place: It's the same basic idea as the recycle bin on your desktop. Any buckets or objects left in the recycle bin for long enough become eligible to be deleted, which then makes the backend go and securely erase things. Effectively, any bits of metadata in the soft deletion corner are still considered garbage collection roots, they're just not shown when you do a normal call. The real fun comes into play when you remember that Tigris has a globally replicated active-active database where any region can change any object at any time. Most of the time things work out and objects are replicated without too much strife. The annoying part comes when two events are ordered weirdly. Imagine a scenario where one agent in one datacentre deletes an object after another agent in another datacentre: How would this replicate out? Well for one each change is timestamped by when it's done in terms of Unix nanoseconds, so the replication messages kinda look like this: This means that in theory, a user could DELETE an object before an update is processed by another region, and that would make the regions disagree about if the object exists or not. This is a horrible state to be in and usually requires support intervention or to recreate/re-delete the object. The root cause boils down to deleting objects actually deleting metadata from the database doesn't scale past a single region. Updates to metadata include the entire metadata object, so if you delete it locally and a new version is pushed remotely, the object will gain the remote state. We don't want users to have to deal with that, so we added the concept of anti-resurrection to Tigris. Any write to an object must prove it is newer than the deletion. In this circumstance, a user sent a DeleteObject request to the IAD datacentre at time 25, but an agent sent a new version of the object with PutObject to the ORD datacentre at time 15. The user's delete is newer than the agent's put, so the new version is rejected and the delete gets sent back to ORD. Tigris extends the S3 API by having users add headers to their requests. For example, to create a bucket with soft deletion enabled: Or to list soft-deleted objects: Or to permanently delete one soft-deleted version: When you have a soft-delete enabled bucket, you can also forcibly delete an entire bucket: Warning If you use this call on a bucket that doesn't have soft deletion enabled, you have permanently deleted your bucket. Please call this with care. Support cannot help you if you use this call wrongly. And then bring it back from the dead: Object storage entered our stacks as an unlimited FTP server we all used for backups. A distressing amount of the world's most important data lives in object storage buckets because it's the best place to put it. This is why having an "undo" button matters, it's what makes it safe to trust your backups in the cloud. To err is human, and mistakes are a "when" to plan for, not an "if" that you hopefully never have happen. The blast radius of one overly wide flag is measured in years of people's lives. One of the biggest usecases that comes to mind is ransomware prevention. Imagine a case where an attacker downloads everything in your bucket, deletes it, and asks for a ransom to send you the files back. With Tigris, soft deletes means that the ransom can be ignored, you can un-delete your data, and be on your merry way with incident response. The other big usecase is for agents, where they somehow get the idea that deleting production data is the right way to solve a problem. Both cases mean you need a quick and fast way to go back to before things went wrong. If you want true isolation instead of recovery, that's why we have bucket forking . Bucket forking needs to be enabled before a bucket is created, but you can enable soft deletion on any bucket in the dashboard whenever you want. Every storage system is going to make you choose between ones that hide how the platform works and ones that expose the gorey internals to users. I think that hiding the internals and exposing the high level operations built on top of them is the right way to go, if only because the higher level operations are much easier to make safe in our globally distributed future. Enable soft delete on any Tigris bucket, new or existing, and every delete becomes recoverable for up to 90 days. Restoring a whole bucket is one call. Read the soft delete docs .
Brilliant. I'm such a "valued customer" that they couldn't even be arsed to put my name in the email. Why is it even necessary to have a "business intelligence database" with a 3rd party? I ordered a fucking laptop. Can a tech company not create their own customer database? Full email here - https://cdn.kevquirk.com/framework-breach-email.pdf Thanks for reading this post via RSS. RSS is ace, and so are you. ❤️ You can reply to this post by email , or leave a comment .
MatchBox: A Semantic Foundation for Data Plane Portability Eric Hayden Campbell, Robert Zhang, Divyanshu Saxena, Aditya Akella, and Işıl Dillig PLDI'26 This paper identifies problems associated with subtle differences in match-action table implementations across hardware vendors and proposes some formalism to allow generic tooling to be implemented for match-action tables. A match-action table is a data structure present in some NICs and switches which specifies how packet-processing hardware should modify packets on the fly. This post on Gigaflow also discusses how a virtual switch can be implemented with match-action tables. Fig. 2 shows two match-action tables programmed in a hypothetical switch ( IP addresses in these tables are written in CIDR syntax ): Source: https://dl.acm.org/doi/10.1145/3808277 The syntax is clear but the semantics have an important footnote: switch S has a policy which causes packets that miss in the routing table to be dropped. Now imagine a switch ( ) from another vendor with a different policy: packets which cause a miss in the routing table are broadcast to all output ports. The task of porting the match-action tables from to in a way to preserves behavior is non-trivial. Fig. 3 contains a correct solution: Source: https://dl.acm.org/doi/10.1145/3808277 The difference is in the ACL table. The permissive allow entry has been replaced with two more restrictive entries that only allow packets that would not have triggered a miss in the routing table. One automated way to compute the contents of the ACL table for switch is an algorithm that looks at all pairs (i.e., the Cartesian product) of entries in the route and ACL table for switch , and then drops pairs that don’t make sense (e.g., the route and ACL addresses have no overlap). If you squint at that definition, it looks a lot like a relation join operation. In other words if you think of the ACL and routing tables as relations, then a way to compute the ACL table for switch would be to join the route and ACL tables for switch . The authors argue that relational algebra is almost the correct hammer for this nail, but not quite, and so this paper proposes Match Algebra . In Match Algebra, a match-action table can be thought of as a partial function which maps a valuation to an (action, valuation) pair. A valuation is just a set of bits (extracted from packet headers), and an action describes how a packet is to be modified. Another way to think of a match-action table is an ordered set of rules. A rule comprises: A guard, which defines the set of packets that match the rule An (action, valuation) pair Example guards could be: IPv4 packets with source address matching 10.2.1.0/24 UDP packets with a destination port of 15354 or 15355 An example (action, valuation) pairs could be: (replace the destination port, 15356) (pass the packet through unmodified, x) The set of rules is ordered such that if guards associated with multiple rules apply to a particular packet, the highest priority rule wins. The most important operators in the Match Algebra are: Sequential composition: modify the packet according to table , and use the result as input to table Preferential composition: Check to see if table has a rule matching the incoming packet, if so then apply that rule. Otherwise, use table to modify the packet. Parallel join: apply tables and to the input packet to generate two (action, valuation) pairs: , . Merge the results together. The merge operation requires that the results from and do not overlap (e.g., causes a destination port to be modified while causes destination address to be modified). The paper describes some other operators and presents formal semantics for Match Algebra. The paper describes which is a language (embedded in OCaml) which operates at the Match Algebra level of abstraction. Fig. 13 shows an example program which transforms match action tables with operators from Match Algebra: Source: https://dl.acm.org/doi/10.1145/3808277 Results The paper presents the following real-world use cases of : Transforming a set of match-action tables to an equivalent set with a different form (for porting rules between switches) Porting firewall rules between AWS, GCP, and Azure (which each have a different required structure) Translating system-wide eBPF tables to per-CPU eBPF tables Thanks for reading Dangling Pointers! Subscribe for free to receive new posts. Source: https://dl.acm.org/doi/10.1145/3808277 The syntax is clear but the semantics have an important footnote: switch S has a policy which causes packets that miss in the routing table to be dropped. Now imagine a switch ( ) from another vendor with a different policy: packets which cause a miss in the routing table are broadcast to all output ports. The task of porting the match-action tables from to in a way to preserves behavior is non-trivial. Fig. 3 contains a correct solution: Source: https://dl.acm.org/doi/10.1145/3808277 The difference is in the ACL table. The permissive allow entry has been replaced with two more restrictive entries that only allow packets that would not have triggered a miss in the routing table. One automated way to compute the contents of the ACL table for switch is an algorithm that looks at all pairs (i.e., the Cartesian product) of entries in the route and ACL table for switch , and then drops pairs that don’t make sense (e.g., the route and ACL addresses have no overlap). If you squint at that definition, it looks a lot like a relation join operation. In other words if you think of the ACL and routing tables as relations, then a way to compute the ACL table for switch would be to join the route and ACL tables for switch . The authors argue that relational algebra is almost the correct hammer for this nail, but not quite, and so this paper proposes Match Algebra . Match Algebra In Match Algebra, a match-action table can be thought of as a partial function which maps a valuation to an (action, valuation) pair. A valuation is just a set of bits (extracted from packet headers), and an action describes how a packet is to be modified. Another way to think of a match-action table is an ordered set of rules. A rule comprises: A guard, which defines the set of packets that match the rule An (action, valuation) pair IPv4 packets with source address matching 10.2.1.0/24 UDP packets with a destination port of 15354 or 15355 (replace the destination port, 15356) (pass the packet through unmodified, x) Sequential composition: modify the packet according to table , and use the result as input to table Preferential composition: Check to see if table has a rule matching the incoming packet, if so then apply that rule. Otherwise, use table to modify the packet. Parallel join: apply tables and to the input packet to generate two (action, valuation) pairs: , . Merge the results together. The merge operation requires that the results from and do not overlap (e.g., causes a destination port to be modified while causes destination address to be modified). Source: https://dl.acm.org/doi/10.1145/3808277 Results The paper presents the following real-world use cases of : Transforming a set of match-action tables to an equivalent set with a different form (for porting rules between switches) Porting firewall rules between AWS, GCP, and Azure (which each have a different required structure) Translating system-wide eBPF tables to per-CPU eBPF tables
Good morning premium subscribers! As ever, please ping me at [email protected] if you have any questions. Oracle has one of the strongest mythologies in the tech industry. Ask a regular person and they’ll tell you that it’s “incredibly profitable” and “growing fast,” that it’s “unstoppable,” and that Larry Ellison has the mandate of heaven with regard to the continual sales of software and hardware related to databases and AI. And those people are completely and utterly wrong. The original title of this article was “Is Oracle Dying?” because I assume, when I took a deeper look, that there’d be some sort of debate , some sort of bull case for a decades-old quasi-hyperscaler run by one of the more nakedly-evil CEOs in the history of tech. I assumed — incorrectly, I might add — that Oracle as a business was doing fine other than the ridiculous commitments it made to support the whims of Sam Altman and OpenAI via deals that I believed (and still believe) will kill Oracle . Except it turns out that Oracle has already been on a death spiral for the best part of a decade (if not longer) and has only survived this long by screwing its customers, taking on masses of debt, and — most importantly — more than $85 billion in acquisitions over the last 23 years. Pretty much every major product line outside of databases is a hodge-podge of other people’s innovation stapled together with a legendary contempt for the customer . These acquisitions (and continual price increases ) are the only thing keeping the reaper from Oracle’s door other than margin-destroying GPUs . And that’s why Oracle’s revenue looks like this : After April 2009’s $5.7 billion acquisition of Sun Microsystems , Oracle’s revenues barely kept pace with inflation until December 2021’s $28.3 billion acquisition of Cerner allowed it to create Oracle Health , adding about $6 billion in annual revenue that had 40% lower margins (about 21.7%) than Oracle’s other businesses , though Oracle immediately started closing offices and brutal layoffs to try and bring them up. And as I mentioned above, Oracle’s other plan was to sink a little over $99 billion in capital expenditures since the middle of calendar year 2020 into AI GPUs. Anyway, let’s see what that’s done to margins - OH MY GOD ! Oracle is a decades-long mission to keep reapplying lipstick to a pig. Billions of dollars of acquisitions have, for the most part, only succeeded in keeping the company’s revenue growth from going negative, and as noted by forensic accountant Howard M. Schilit , this is one of the most well-documented cases of accounting shenanigans being used to cover up that a business is in decline. Today’s newsletter is a sequel to the Hater’s Guide To Oracle , where I told the sordid tale of how Larry Ellison grew a massive, lucrative business out of a database business that one reporter once told me was a “ law firm with a database company attached ,” an Enterprise Resource Planning (ERP) product that competes with SAP to create the most-annoying way to run a large company, and a business built around licensing Java that exists mostly to email people and say “you need to pay us for Java or we’ll sue you.” Then, as I’ve mentioned, there’s Oracle’s cloud infrastructure business, a decade-old also-ran that was meant to compete with Microsoft Azure and Amazon Web Services, but only managed to catch up following the advent of AI GPUs and a movement where all it took to party was buying billions of GPUs and saying “gosh darn, we love AI.” I originally started drafting this as a much tamer piece where I’d ask whether Oracle was dying, but as my editor and I started digging into the research, it became obvious that not only is Oracle dying , it’s been dying for years , kept alive through decades of acquisitions and a desperate and dangerous commitment to generative AI. And AI, I believe, will be what eventually kills Oracle dead. In the past, all Oracle had to do to survive was buy somebody else’s company and replace its flagging revenues with theirs, turning the screws on their customers and laying off as many people as necessary to balance the books. While chaotic and decaying, Oracle’s empire has kept above water by never overextending itself, always keeping a positive free cashflow , and generally avoiding buying into industry hype cycles outside of whatever SaaS vehicle might potentially plug the gap in its earnings. Yet with AI, Oracle broke its long-standing trend of letting someone else figure out the innovation, choosing instead to build its own cloud infrastructure, spending more in capex in its last fiscal year ( $55.6 billion ) than it did in the previous nine years combined ($50.4 billion), tripling its debt from $56.91 billion in FY2017 to $167.4 billion in FY2026, a year that ended with its free cashflow sitting at negative $23.69 billion. For comparison, Oracle has had positive free cashflow every single year since 2001, including the Great Financial Crisis and COVID. Oracle has doomed itself with its commitment to the AI bubble. It has committed to building 7.1GW of data center capacity for one company — OpenAI — as part of a $300 billion, five-year-long contract that requires it to build an impossible amount of capacity in an impossible period of time for a client that could never afford the $70 billion or more in annual costs to make any of it worth it. Today I am going to talk trash on what I consider to be one of the single-worst companies in the tech industry that’s survived only through financial engineering and never, ever overextending itself. With revenue plateauing and customers in revolt, Oracle’s future already looked murky, but with the power of AI — and $95 billion in FY2027 capex — it’s becoming increasingly clear that this may be Larry Ellison’s last dance with Silicon Valley. This is the Hater’s Guide To Oracle Part 2, or AIpoaclypse Now.
Breadcrumb Filters: Fast Fully Featured Filters Andrew Krapivin, Aaditya Rangarajan, Alex Conway, Martin Farach-Colton, Rob Johnson, and Prashant Pandey SIGMOD'26 This paper presents the design of a breadcrumb filter , which is a membership testing data structure . Unlike a Bloom filter , a breadcrumb filter supports operations like deletion and merging. Breadcrumb filters also have the nice property that most operations access a single cache line (most of the time). A breadcrumb filter is a fingerprinting filter . Each item in a set is represented by its fingerprint (i.e., hash). Say a filter contains 1024 cache lines, and each cache line has storage for items. To insert an item into the filter, compute a 16-bit fingerprint of the item. Decompose that into a 10-bit integer (the cache line index) and a 6-bit integer (the remainder). Use the cache line index to determine which cache line to access. Find an empty slot in that cache line and place the remainder bits of the fingerprint into the empty slot to represent the item. A breadcrumb filter builds on top of these mechanics by cleverly dividing the filter storage into two sections: the front and back yards. The front-yard represents the fast path: each filter operation will touch one front-yard cache line. The backyard is only used to handle cases where a front-yard cache line fills up. The paper hyphenates “front-yard” but writes “backyard” as one word. The following pseudo-code illustrates how an item is inserted into a breadcrumb filter: A lookup operation follows a similar structure: To delete an item from a breadcrumb filter, it is sufficient to delete the item’s fingerprint . That wasn’t obvious to me up front. Imagine two items have the same fingerprint (hash). Inserting them both causes the same fingerprint to be inserted twice. Now, when one of them is deleted, it suffices to delete one of the copies of the fingerprint in the breadcrumb filter. The trick with deletion is that deleting a fingerprint from a front-yard cache line can require promoting an item from an associated backyard cache line. The real magic with breadcrumb filters comes in how items are moved between the front-yard and backyard. If a front-yard cache line is found to be full during insertion, then one item is moved to the backyard. That item could be the one that is currently being inserted, or it could be an item that was previously placed into the front-yard. The policy is: move the item which has the greatest value of the remainder bits . For example, if two items (A, and B) have remainder bits of 23 and 7, then item A will be moved to the backyard before B. This enables lookup operations to avoid touching backyard cache lines. For example, say the item that is being searched for has remainder bits = 23, and the (full) front-yard cache line contains items with remainder bits = [12, 5, 34, 3], there is no need to search the backyard. The “34” in the front-yard implies that no item with remainder bits value less than can be in the associated backyard cache lines. Note that this policy requires that delete operations sometimes move items from the backyard to the front-yard. The other trick is a mapping between front-yard and backyard cache lines which enables promotion of a deleted item from backyard to front-yard. Say each front-yard cache line is associated with two backyard cache lines, but those backyard cache lines are each associated with many front-yard cache lines. A front-yard cache line index is represented with 10 bits: The two backyard cache line indices associated with that front-yard cache line are: The key here is that very little information needs to be stored in the backyard in order to allow mapping from a backyard cache line index to a front-yard cache line index. To map backyard index back to , all one needs to know is the value of bit (which is stored in the backyard cache line). When an item is deleted from a front-yard cache line, the two associated backyard cache lines are searched for an item to be promoted back to the front-yard. Metadata (e.g., the value of bit ) is used to ensure that items are promoted back to the front-yard cache line from whence they came. Fig. 9 compares the throughput of the breadcrumb filter (BCF*) against other filters: Source: https://dl.acm.org/doi/10.1145/3786629 Dangling Pointers This design agrees with many others that the best one can do is read a single cache line for each lookup. I don’t have a better solution in mind, but it seems painfully slow if the filter doesn’t fit in cache. Thanks for reading Dangling Pointers! Subscribe for free to receive new posts.
I’m at RubyConf this week, and it’s great! I recently read that lobste.rs is now running on SQLite . One part from the post caught my attention: I wish we could say in a test, “Fail if you encounter any full table scans”. Which would have caught the perf issues we experienced during the first deploy. SQLite collects information about prepared statements and exposes those statistics though an API . The upshot of this is that we can tell whether a statement did a full table scan after executing the statement without using an . Here’s an example program that demonstrates detecting a query did a full table scan: Feels like we could integrate this in to Rails and warn or raise in test / development. I’m not sure if we’d want to check this all the time in production, but maybe it would be fine?
RABIT: Efficient Range Queries with Bitmap Indexing Junchang Wang, Fu Xiao, and Manos Athanassoulis SIGMOD'26 This paper presents an optimization for range filtering (e.g., ). File this under: “so crazy it might actually work”. This paper builds on the concept of a bitmap index . If the cardinality of a column is (i.e., there are distinct values in the column), then a bitmap index stores additional 1-bit columns along with the original column. These additional columns are called point bitvectors . The value in additional column is 1 for a particular row if the value in that row is the th distinct value. Here is an example column with 6 rows and 4 distinct values (0, 1, 2, 6). The header indicates that this is the value column. And here is the same column with 4 additional 1-bit wide rows attached. The header indicates columns that hold point bitvectors. To find all rows which have a value of 2, simply read the 3rd (i.e., ) bitmap column. Similarly, to find all rows which have a value of 6, simply read the 4th bitmap column. To efficiently support range queries, the authors of this paper propose adding even more columns that hold 1-bit values. These columns are called cumulative bitvectors . A cumulative bitvector holds the bitwise-or of a set of point bitvectors. In the example above, let’s create a cumulative bitvector (named ) for the values 0 and 1. The value of this column for a given row will be 1 if the value contained in the row is either 0 or 1. In other words: . Similarly, we can create a cumulative bitvector for the values 2 and 6 using the equation: . Here is the full turkey: A range query can be executed by reading one or more cumulative bitvectors and possibly a few point bitvectors. For example, to find all rows that have a value < 2, all one needs to do is read the value of . Cumulative bitvectors do not add much value in this toy example because each cumulative bitvector only aggregates data for two values, but you can see how this could work well with more aggregation. This trick can even be made to work for range queries that partially overlap with a cumulative bitvector. This whole scheme relies on the fact that point and cumulative bitvectors are highly compressible. This paper assumes the use of WAH compression . The executive summary of WAH compression is to divide each bitvector into words (e.g., 32 or 64 bit). One bit of each word is metadata that determines if the word is a or a . The remaining bits of a literal word contain raw (uncompressible bits). The remaining bits of a fill word contain a value and a length (run-length encoding). Fig. 9 compares throughput of this scheme (labeled GE in the figure) to other work. means each cumulative bitvector aggregates data for 20 point bitvectors. Performance looks good even for columns holding 100K distinct elements. Source: https://dl.acm.org/doi/10.1145/3769819 Table 3 compares the storage requirements for this scheme versus other indexing schemes that support range queries, which seems too good to be true. Source: https://dl.acm.org/doi/10.1145/3769819 Dangling Pointers I wonder if this idea could be generalized to other types of filtering, such as string operations (e.g., . Thanks for reading Dangling Pointers! Subscribe for free to receive new posts.
The Kamal setup guides I found online focus on S3 backups using . You don’t want that for a production database. A better solution is to set up your Postgres database for Point-In-Time Recovery (PITR) using WAL-G or pgBackRest. This means your database is continuously archiving WAL segments to an S3 bucket (roughly every 60 seconds), so you can restore to any point in time. With LLMs, it’s not that hard to set up. This quick guide focuses on WAL-G, because I’ve found it to be a lot easier to set up than pgBackRest.
How does the database decide on the order, when it is not specified? What about performance? Can returned pages overlap? Meaning: might item from page 1 suddenly appear on page 2, even if the underlying data stays the same?
In short: I prefer strict tables in SQLite because they avoid some datatype problems, such as putting text in number columns. SQLite has a feature that I think is underrated: strict tables . Strict tables help enforce rigid typing, preventing mistakes like putting text into integer columns. I like them, and wrote this post to promote their use! To make a strict table, add to the end of its definition. Like this: That’s it! But what does it do? Broadly, strict tables help enforce rigid types, like other SQL engines do. Most significantly, strict tables keep you from inserting the wrong type into a column. For example, SQLite normally lets you put text into an column, but not with strict tables. Personally, I think it’s a mistake to try to put text in an integer column, or vice-versa. I don’t want SQLite to let me make this error! The same validation happens for s, too. Notably, if a value can be losslessly converted, it will still be accepted. For example, the string can be perfectly converted to an integer, so it’s allowed. These two lines are equivalent, even for a strict table: By default, you can create columns with bogus types. For example, all of these work even though they aren’t valid SQLite datatypes: I think these aren’t what the developer intended. Some of these are typos, some of them are misunderstandings of which datatypes SQLite supports , and some are egregious mistakes. Appending to any of these statements makes them error. In my opinion, that’s the correct behavior! Only , , , , , and are allowed. Strict tables also require a column type, so you can’t do . If you still need a column to be flexible, you can use the datatype. As the name suggests, it allows anything—even in a strict table. I haven’t found a use for this, but maybe you will! I prefer strict tables but I must share a few cons. Not everything is better! I think it’s best to use strictness from the start, but that’s not always possible. Unfortunately, I don’t think there’s a way to a table to make it strict. I think you have to copy the data out of the non-strict table into the strict one. Something like this: Note that this could be tricky if the non-strict table has invalid data! For example, if the old data accidentally contains text in an integer column, you’ll get errors when doing the migration. You’ll probably need to clean the data or cast it . You could make a rule for your codebase that all new tables are strict. That might be useful—at least some of your tables are valid! But it might also mean you have inconsistent validation across your tables, which might be more surprising than having weak validation on all tables. It’s up to you to decide whether this is a good fit for you. SQLite has a whole page called “The Advantages Of Flexible Typing” , where they argue that SQLite’s flexible behavior is good, actually. I hesitate to wade into the controversy of static-versus-dynamic, but I disagree in most cases. I’ve personally encountered many bugs where an unexpected data type caused subtle headaches. I’d much rather these mistakes explode loudly. But it’s worth noting that SQLite’s developers seem not to share my preference for strict tables! They point out a few good uses for flexible tables, such as “a pure key-value store” or “a place to store miscellaneous attributes” of different types. They also mention that you might want to keep the invalid data in some cases, like if you’re directly importing a messy CSV and don’t want to lose any data. I still prefer strict tables, but acknowledge there are some reasonable cases for non-strict ones. (There’s also at least one comment in the SQLite source that calls non-strict tables “legacy” , but I trust that less than the official documentation.) SQLite introduced strict tables in version 3.37.0 , released November 2021. If you’re on an older version of SQLite, you can’t use strict tables. It’s worth noting that old versions of SQLite can’t read databases with strict tables. For example, if you create a strict table in the newest version of SQLite and then try to read that database in SQLite 3.36.0 (before strict tables were added), you’ll get an error—even if the strict table is already in the database. Strict tables are theoretically slower because they have to do a little extra work. For example, they check datatypes when doing an insert or update . But in practice, I don’t think this is an issue. I wrote a hacky script that inserted millions of rows into a table with 100 columns, and there was no obvious difference on multiple machines I tried. The file size on disk was also the same. I didn’t test this thoroughly, so maybe there’s something I missed, but I don’t think strict tables present a performance problem. In fact, one might expect better performance because you won’t be accidentally mismatching SQLite’s column affinities. But again, I haven’t tested this. Personally, I think the pros of strict tables outweigh the cons. I generally prefer when types are rigidly enforced. It squashes a class of mistakes, and help enforce good data integrity. They’re not a panacea, but they’re usually easy to add and go a long way. If there’s a SQLite feature you think is underrated, please tell me .
This morning I released sqlite-utils 4.0 , the 124th release of that project and the first major version bump since 3.0 in November 2020. In addition to some small but significant breaking changes (described in this upgrade guide ), this version introduces three major features: database migrations , nested transactions (via a new method), and support for compound foreign keys . Schema migrations define a sequence of changes to be made to a SQLite database, plus a mechanism for tracking which migrations have been applied and applying any that are found to be pending. Migrations are defined in Python files using the sqlite-utils Python library , which includes a powerful method providing enhanced alter table capabilities that are not supported by SQLite's statement. ( implements the pattern recommended by the SQLite documentation - create a new temporary table with the new schema, copy across the data, then drop the old table and rename the temporary one in its place.) Here's an example migration file which creates a table called , adds an additional column to it in a second step, then changes the types of two of the columns in a third: Save that as and run it against a fresh database like this: Then if you check the schema of that database: You'll see this SQL: The table is used to keep track of which migration functions have been run. The table above is the schema after all three migrations have been applied. To see a list of migrations, both pending and applied, run this: If you don't specify a migrations file, the command will scan the current directory and its subdirectories for files called and apply any instances it finds in them. You can also execute migrations from Python code using the method, which is useful for building tools that manage their own database schemas over multiple versions. My own LLM tool has been using a version of this pattern for several years now, as shown in llm/embeddings_migrations.py . My favorite implementation of this pattern remains Django's Migrations , developed by Andrew Godwin based on his earlier project South . Fun fact: Andrew, Russ Keith-Magee, and I presented our competing approaches to schema migrations for Django on the Schema Evolution panel at the very first DjangoCon back in 2008! My attempt was called dmigrations , developed with a team at Global Radio in London. Django's migrations can be automatically generated from model definitions and include the ability to roll back to a previous version. The approach is deliberately simpler: unlike Django, encourages programmatic table creation rather than a model definition ORM, so there isn't anything we can use to automatically generate migrations. I decided to skip rollback, since in my experience it's a feature that is rarely used. With a SQLite project, an easy way to achieve rollback is to create a copy of your database file before you apply the migrations! The design of migrations is three years old now - I had originally released it as a separate package called sqlite-migrate , which never quite graduated beyond a beta release. I've used that package in enough places now that I'm confident in the design, so I've decided to promote it to a feature of to make it available by default to all of the other tools in the growing sqlite-utils/Datasette/LLM ecosystem. I made one last release of , which switches it to depend on and replaces the file with the following: Any existing project that depends on should continue to work without alterations. Here are the release notes for this version, with some inline annotations: The 4.0 release includes some minor backwards-incompatible fixes (hence the major version number bump) and introduces three major new features: I think of migrations as the signature new feature, hence this blog post. has long had a confused relationship with database transactions, partly because when I started designing the library back in 2018 I didn't yet have a great feel for how those worked in SQLite itself. Adding migrations to the core library made me determined to finally crack this nut, since transactions make migration systems a whole lot safer and easier to reason about. I ended up building this around a context manager which looks like this: SQLite supports Savepoints , and as a result can be nested to carry out transactions inside of transactions. It's pretty neat! This came about when I asked a coding agent to review all open issues and PRs for things that should be included in a 4.0 release since they would represent breaking changes if I added them later, and it correctly identified that compound foreign keys were exactly that kind of feature. I started with a breaking change to the table.foreign_keys introspection method, and then decided to see if Claude Fable 5 could handle the more fiddly job of integrating compound foreign key creation into the library. The API design it helped create felt exactly right to me - consistent with how the rest of the library worked already. Other notable changes include: This was the change that first pushed me to consider a breaking-change 4.0 version bump. I built this to help support sqlite-chronicle , which uses triggers to keep track of rows in a table that have been inserted, updated or deleted. Probably the most disruptive breaking change - I've had to update a few places in my own code to switch from to as a result. The flag was a later addition to allow column types (text, integer, real) to be automatically detected based on the data in a CSV. It should be the default, and releasing a 4.0 means I can make it so. The oldest issue addressed by this release - the underlying bug was opened (by me) in October 2020. See Upgrading from 3.x to 4.0 for details on backwards-incompatible changes. The detailed release notes for the features and fixes shipped during the 4.0 pre-release cycle are available in 4.0a0 , 4.0a1 , 4.0rc1 , 4.0rc2 , 4.0rc3 and 4.0rc4 . The upgrade guide was entirely written by Claude Fable 5, Claude Opus 4.8 and GPT-5.5. The same is true of the release notes. This is the kind of documentation I've slowly become comfortable outsourcing to the robots. It doesn't need to convince people of anything, or express any opinions - its job is to be as accurate and detailed as possible. I've reviewed the release notes closely and can confirm they are accurate and comprehensive. I released the first alpha of sqlite-utils 4.0 over a year ago . I've been dragging my heels on the stable release because of the amount of work it would take to track down and clean up the many other minor design flaws that a major version number allowed me to take on. Assistance from Claude Fable 5 (and to a lesser extent Opus 4.8 and GPT-5.5) gave me just the boost I needed to overcome inertia and make the most of the time I could afford to spend on this library. Fable has really good taste in API design, and is relentlessly proactive if you give it a more open goal. My most successful prompt was a review task that I issued against what I thought was the last release candidate: I tried this with GPT-5.5 xhigh in Codex Desktop and Fable 5 in Claude Code. GPT-5.5 wrote 5 Python scripts and didn't turn up anything particularly interesting - its final report is here . Fable 5 wrote 12 scripts , identified 4 release blockers and 10 additional issues in its report , and built a neat combined repro script , which, when run, output the following: I found myself agreeing with almost all of them. Here's the PR with 16 commits where we worked through them in turn. There's no doubt in my mind that sqlite-utils 4.0 is a significantly higher-quality release than if I had built it without the assistance of the latest frontier models. You are only seeing the long-form articles from my blog. Subscribe to /atom/everything/ to get all of my posts, or take a look at my other subscription options . Database migrations , providing a structured mechanism for evolving a project’s schema over time. ( #752 ) Nested transaction support via , plus numerous improvements to how transactions work across the library. ( #755 ) Support for compound foreign keys , including creation, transformation and introspection through table.foreign_keys . ( #594 ) Upserts now use SQLite’s syntax, detect existing table primary keys automatically and reject records that are missing required primary key values. ( #652 ) now executes immediately and rejects statements that do not return rows; use for writes and DDL. CSV and TSV imports now detect column types by default, while inserts into existing tables preserve those tables’ column types. ( #679 ) and no longer create lookup table records for all- values. ( #186 )
Accelerating Stream Processing Engines via Hardware Offloading Zhengyan Guo, Mingxing Zhang, Yingdi Shan, Kang Chen, Jinlei Jiang, and Yongwei Wu SIGMOD'26 This paper describes a trick to offload partitioning from CPU to NIC via clever use of RSS. The context of the paper is distributed systems for processing streaming queries, but the trick seems applicable to databases in general. Hash partitioning is a common divide-and-conquer technique to implement joins and aggregations. Here are some posts about papers that use this partitioning: SPID-Join: Skew-Resistant In-DIMM Joins Breaking Through the Memory Wall of OLTP Systems with PIM High-Performance Query Processing with NVMe Arrays: Spilling without Killing Performance Efficiently Processing Joins and Grouped Aggregations on GPUs RSS is a NIC feature whereby the NIC hashes select fields from incoming packet headers and uses the result to determine which CPU core to send the packet to. This enables efficient load balancing across CPU cores without reordering packets within a given flow (i.e., connection). Here is a previous post describing a clever way to extract more value out of RSS in cloud VMs: Enabling Fast Networking in the Public Cloud If you have many nodes cooperating to process a query, then the hash partitioning may span many nodes. For example, node A could hash the join/aggregation key of each row and then forward the row to either node B, C, or D, E depending on the hash value. This enables the join/aggregation work to be split across nodes B, C, D, and E. This is all fine and dandy from the perspective of node A. However, nodes B, C, D, and E likely have multiple CPU cores. How can one of these nodes execute their join/aggregation in parallel? The answer is recursive: partition the incoming rows again (using a different hash function) and have each CPU core process one of these smaller partitions. The paper focuses on the cost of partitioning the dataset, which can cost just as much as the partition join/aggregation step that follows it. The key insight is that the partition algorithm looks a lot like the RSS load balancing algorithm present in the NIC hardware. Here is the punchline: establish multiple network connections (using different ports) between node A and each of nodes B, C, D, and E. When node A partitions rows, it determines a specific connection (not node) to send each row to. This doesn’t improve performance at the sender, but it dramatically helps the receivers. Each receiver configures RSS such that all connections are spread across the CPU cores on the receiver. The NIC then distributes received packets to the appropriate CPU cores without any partitioning work on the receiving nodes. The one downside to this approach is load imbalances that occur due to data skew. If some join/aggregation keys are more common than others, then some CPU cores may be assigned more work than others. The paper proposes to dynamically monitor load imbalance at each receiver and reconfigure the RSS settings of the NIC to move connections off hot cores. Section 5 of the paper describes synchronization necessary to move a connection between cores in the middle of the query. This is a good mitigation, but as we’ve seen in this paper , RSS configuration is not uniformly exposed on cloud VMs. Fig. 8 has performance results across a number of benchmarks: Source: https://dl.acm.org/doi/10.1145/3769754 Dangling Pointers The solution is great, but asymmetric. I wonder if there is a way to get similar benefits on at the sending node (send side scaling)? Thanks for reading Dangling Pointers! Subscribe for free to receive new posts.
For roughly the last ten years, a meaningful percentage of my working hours have been spent thinking about observability. If you're not familiar with the term, "observability" is what we call it now that "monitoring" doesn't sound expensive enough. The actual work is unglamorous in that you collect a lot of logs, some metrics, a few traces, and then you give them to people. I generally like my job. I like that we're always trying new ideas and approaches. I like the fact that when things go wrong, the answer is almost always sitting there in the data, waiting to be found by whoever is patient enough to look. But I want to be honest with you: in ten years of doing this work, across a half-dozen companies and every observability platform you've heard of and a few you probably haven't, logs have never stopped being the worst part of the job. They were the worst part when I started. They are the worst part today. I fully expect them to be the worst part of this job forever until the robots rise up and rip my head off in one clean sweep. I've written about why logs are terrible before , so I'll spare you the full lecture and give you the short version. Every developer's expectations for logs are set by a single formative experience: the syslog box. Or a container running locally. Or tail -f on a production server they probably shouldn't have SSH'd into. The point is that at some early, tender moment in their career, they had an experience with logs that was flawless. They ran and something useful came back. They piped it into jq and got exactly what they needed. This experience is the observability equivalent of a first kiss. It ruins them for everything that comes after. Because here is the thing about that flawless experience: it works because the system is small, the volume is trivial, and the person querying is the same person who wrote the log line. There is no schema drift, no cardinality explosion, no cross-team consumer with dashboard expectations, no VP asking why the "revenue events" graph has a gap in it. Then there are forty services. Now there are four hundred. Now the logs are being consumed not just by developers but by customer service, who need to look up a specific user's failed checkout from Tuesday. And by the data team, who are quietly building a business-critical dashboard on top of a log line that a backend engineer is about to refactor without telling anyone. And by the on-call, who at 3 AM does not want to learn a new query language, does not want to think about index patterns, and would like the search bar to just work. So you have a technical problem — the volume is enormous, the shape is inconsistent, the queries are unpredictable — sitting on top of an expectations problem, which is worse. Developers want logs instantly, they want to run arbitrary operations on them, and they will not commit to a schema. Meanwhile the less-technical consumers of that same data want the dashboards to be stable forever, the UI to be forgiving, and the whole thing to feel like a normal product. These two audiences are, in most practical respects, at war with each other, and you are the diplomat. ClickHouse came out of Yandex, where it was built to chew through analytical queries against absurd volumes of clickstream data. It was not designed for observability. It just happens to be shockingly good at it, because clickstream data and observability data have a lot in common: high volume, append-heavy, time-ordered, mostly read in aggregate, and every so often you need to reach in and find one specific needle. You can run it yourself with Helm charts. You can point Grafana at it via the ClickHouse plugin, or use their own web UI, or bring your own frontend. Their docs are actually good, which I mention because it's rare enough to be worth flagging. I've never used their ClickStack setup though, so YMMV. For observability specifically, the OpenTelemetry Collector has a ClickHouse exporter, which means you can pipe OTLP data straight in and let it manage the initial schema for you. ClickHouse is designed to scan billions of rows and ingest an amount of data that, when you first see the numbers, makes you assume they're lying. They're not lying. You query it with SQL, which is a language that already exists and was not created by a startup two weeks ago. I'm ranting about logs and then I'm explaining why I like to administer Clickhouse more. Let me take a second and explain why Clickhouse is really good at logs at scale. Logs, as a data shape, have some peculiar properties. They're append-only. You never update a log line, and you almost never delete a single one, though you delete a lot of them at once when retention kicks in. They arrive roughly in time order, though never actually in order. They're read in bursts where nobody looks at logs for days, and then during an incident somebody wants to scan a billion of them in seconds. They're highly compressible, because most of the bytes in your logs are repeated: the same service names, the same hostnames, the same error strings, the same JSON keys, over and over and over again. And critically, when you query them, you almost always want either a narrow time range across all fields or an aggregation across a wide time range with a few filters. You very rarely want "give me one specific row by ID" the way you would from a transactional database. (There are exceptions when its something like GDPR or compliance logging which is its own subgenre of nightmares). In a row-oriented database — Elasticsearch, Postgres, MySQL — the data for a single log line is stored together on disk. If your log has 40 fields and your query only cares about 3 of them, tough luck, you're reading all 40 from disk anyway. The database will filter it in memory, but the disk I/O has already happened. ClickHouse stores each column separately. If your query says SELECT service, status_code, count() FROM logs WHERE timestamp > now() - INTERVAL 1 HOUR GROUP BY service, status_code, ClickHouse reads exactly three columns off disk: timestamp, service, and status_code. The other 37 columns in your schema might as well not exist. On observability data, where you often have dozens of attributes but any given query touches three or four, this is the difference between scanning 800GB and scanning 40GB. This is also why the compression numbers look absurd. Columnar data compresses far better than row-oriented data because the values within a single column are, by nature, similar to each other. A column of service_name values might have a hundred distinct strings across a billion rows. ZSTD eats that for breakfast. You'll routinely see 10–14x compression ratios on real observability data, compared to 2–3x for Elasticsearch. The amazing thing is that ClickHouse scales without changing shape. I don't know how else to say this. Every other observability backend I've worked with mutates as it grows. The architecture at 1 TB a day and the architecture at 10 TB a day are recognizably different systems, with different failure modes, different ops burdens, and different mental models. ClickHouse at 10 TB a day looks like ClickHouse at 1 TB a day with more shards. That's it. That's the pitch. That's the whole reason I'm writing this. Let me show you what I mean. At 1 TB a day, every modern observability stack is roughly okay. If you're at this scale, you can pick almost anything and be productive. The differences below are real but they're not yet painful. Here is the honest truth: at 1 TB a day, ClickHouse is not less complicated than its peers. It's roughly the same. Maybe slightly more, if you count the schema design work you have to do up front. You get 10–14x compression with ZSTD and proper codecs, the Altinity Operator handles keeper coordination and the whole thing runs in about seven pods. But you do have to design your schemas. ORDER BY keys matter enormously. There is no native PromQL, so metrics workflows go through the Grafana plugin or through chproxy and an adapter. Roughly $1.5–2.5K/month. If you took the diagrams at this tier and squinted, you'd say they're all in the same weight class. And you'd be right. Now watch what happens next. This is where the exponential curve kicks in for everybody except one of these. You'll notice, if you look at the diagram, that I basically just added shards. That's it. That's the change. Same operator, same query engine, same query language, same mental model. Rebalancing after adding shards is manual, which is a real trade-off — most teams pre-provision or use weighting on Distributed tables to sidestep it. Materialized views for dashboard rollups shift from "nice to have" to "essential." Roughly $7–11K/month. The gap between ClickHouse and everything else opens up here. It doesn't close. This is where most solutions genuinely stop working, in the sense that even a well-staffed internal team cannot keep up with the operational load. If you've read this far, the point is probably already obvious, but I want to say it directly. Every observability stack works at 1 TB a day. If you're small, pick whatever your team already knows. Life is short. We're all just waiting for the robots to kick our heads off like soccer balls. The question is not which stack works today. The question is which stack still resembles itself two years from now, when your data volume has 5x'd and your team has 2x'd and the person who originally designed the whole thing has left the company. Elasticsearch mutates. LGTM mutates. Datadog stays operationally simple but mutates financially into something that requires its own dedicated team of accountants and pipeline engineers just to keep the bill from spiraling. ClickHouse just gets wider. You add shards. That's the whole trick. There is a real cost to this: you have to eat the schema-design and query-engine complexity up front, at a scale where the other options are objectively easier. You will be, briefly, the one making things harder for your developers. They will not always appreciate this. But the trade you're making is that their experience — and yours — remains roughly the same as the data grows by an order of magnitude, and the next order of magnitude, and probably the one after that. I have spent ten years watching observability stacks change shape underneath me while I tried to keep them running. ClickHouse is the first one that hasn't and that has been able to actually scale with me . That's pretty incredible. A relatively vanilla Elasticsearch cluster with Logstash providing some buffer between ingest and the Lucene indexes. Users get full-text search, which is genuinely good — this is the thing Elasticsearch is actually best at, and at this scale it delivers. Mapping explosions are already a background risk with mixed data, so dynamic mapping needs to be disabled or carefully templated from day one. ILM policies (hot → warm → delete) are non-optional even at this size, because forgetting to set them is how you get paged on a Saturday about disk pressure. Roughly $6–9K/month. Nothing too crazy. Alloy (formerly Grafana Agent, RIP) unifies the collection story into a single daemon, which is nice. Loki works well as long as you spend some time educating developers on how to attach useful labels — a conversation you will have many times, with many people, for the rest of your career. Mimir and Tempo largely do what it says on the tin. Roughly $3.5–5K/month. At 1 TB a day, Datadog is genuinely great. This is the scale it was built for, and it shows. You install the agent, you look at dashboards, you go home. There is almost nothing to think about, which is the entire point. You can already see the shape of the cost problem lurking in the diagram — the metered pipelines, the indexed-vs-ingested logs distinction, the custom metrics cardinality tax — but at this scale it's manageable. Roughly $45–75K/month, though negotiated pricing varies enough that I'd take that number with a grain of salt the size of a fist. Datadog's whole pricing philosophy is that they save you a full-time engineer. I think that framing is somewhat deranged, but they are extremely rich and I am not, so consider your source. Kafka is no longer optional. At 5 TB a day, direct writes into Elasticsearch cause bulk-reject storms and backpressure that will absolutely take your cluster down during a traffic spike. So now you're running Kafka, which means you're either running Kafka well or you're about to have a second, entirely different set of problems. Shard math becomes critical — at 50GB target shards, you're minting ~200 shards a day counting replicas, and your cluster state size becomes its own concern. You almost certainly need Elastic's commercial license for searchable snapshots and the frozen tier. Roughly $40–55K/month before licensing. That but Kafka You are now in microservices mode, whether you wanted to be or not. That means 65+ pods across three separate systems, each with its own compaction pipeline, its own hash ring, its own memcached tier. The gossip/memberlist ring becomes a real operational concern; ingester rollouts require careful -ingester.autoforget-unhealthy tuning, and if you get it wrong you either lose data or duplicate it. Roughly $22–32K/month. The operational complexity is still low, in that you don't run any servers. But you now need a full pipeline team whose entire job is reducing your Datadog bill. Exclusion filters, sampling rules, cardinality caps, tag allow-lists, the whole apparatus. This is what I call the "you build a system to avoid using the system you're paying for" trap, and once you're in it, you are in it forever. Roughly $180–350K/month, depending on how aggressive the pipeline team gets. This is also where you are basically fighting with your SaaS provider all the time, pouring over their billing documentation to figure out how to reduce costs. It's a hostile relationship and one I don't enjoy. You are now running three separate Elasticsearch clusters — one for logs, one for metrics, one for APM — federated through Cross-Cluster Search. Hot-tier NVMe cost dominates the bill. This is the scale at which teams start seriously evaluating alternatives, and where a lot of the recent migrations to ClickHouse have originated. Roughly $95–140K/month plus commercial licensing. You need people who are legitimate experts on Elasticsearch. Now thankfully Elastic just laid a ton of those people off, so they're probably possible to get, but still. Running this thing at this size is very complicated . Around 180+ pods, zone-aware everything, split-and-merge compaction, per-tenant limits, shuffle sharding to prevent noisy neighbors. You almost certainly have a dedicated observability platform team of three to five engineers at this point. If you don't, get ready for a bad fucking time. Roughly $55–85K/month. Still very easy to run, in the strict sense that you don't run anything. But your bill is now measured in six or seven figures a month, and the org has almost certainly built a pre-processing pipeline team whose entire existence is dedicated to reducing that bill. Most companies at this scale have gone hybrid: Datadog for APM and high-value metrics, self-hosted (increasingly ClickHouse) for logs. The complexity paradox at this scale is that you now have Datadog's simplicity plus your pipeline complexity plus a second self-hosted stack. Pricing is all over the goddamn place. You might be over a $1 million a month here. Look at the diagram and then look back at the 1 TB diagram. It's the same diagram. There are more shards. That's the difference. Materialized views for rollups are now mandatory rather than optional. Schema design mistakes you made two years ago will start to hurt, so hopefully you didn't make many. Rebalancing after adding shards is still manual; most teams pre-provision or use clickhouse-copier or a dual-write migration when they need to grow the cluster. Kafka starts to become useful as a buffer for very bursty ingest, though it's not required. Roughly $18–28K/month.
AI
Database
Ruby
Performance
Programming
C
Swift
Open Source
DevOps
Data
Business
Cloud
Hardware
Java
Testing
Python
JSON