Pgrust was built: four attempts to rewrite Postgres in Rust with AI

tl;dr After four attempts and dropping $100k, we succeeded in using Opus to rewrite Postgres in Rust. We defined a number of skills and were able to build a repeatable process to rewrite Postgres files into Rust. After running up to 40 concurrent subagents for days, the end result is the 1.8M lines of idiomatic rust code that make up pgrust.

Over the past three months, I’ve been working with my friend Jason Seibel on building pgrust. The idea behind pgrust is we want to show that by leveraging AI, it’s possible to can build a much better version of Postgres. Unfortunately Postgres is written in C and AI still makes a lot of mistakes. For this reason, we started by first rewriting Postgres in Rust. We believe that by having Postgres in Rust it will become a lot easier for AI to safely add new features to Postgres. This thesis is starting to be proven true. Currently in development we have a new, 5th version of pgrust that is faster than Postgres for transactional workloads and is as fast as Clickhouse when it comes to analytical style queries. For context, Clickhouse is hundreds of times faster than Postgres when it comes to analytical queries.

Let us walk you through each of our attempts and what we learned from each approach. We figure for those interested in completely rewriting legacy systems, this post will serve as a useful guide as how to go about such a rewrite of your own.

Attempt #1 – pgrust-og

The first version of pgrust, pgrust-og was initially was going well. It got very close to completion, but ended up having fundamental issues that made it unsalvageable. What I consider to be the root issue is we approached pgrust-og by porting one feature at a time (for contrast in later versions I worked on porting one file at a time).

There were roughly three different phases to the pgrust-og lifecycle:

Foundation

Features

Last Mile

Foundation

Initially I worked on laying out the core foundation of the database. Postgres has a couple of key systems that everything else relies on. To name a few:

The query parser – The parser converts your SQL query into a representation Postgres can understand what data you’re asking for

The query planner – The query planner takes the output from the parser and produces a query plan. A specific way for Postgres to retrieve the data you’re looking for

The executor – Once Postgres has a plan for how to fetch your data, the executor is the one that actually fetches it

Along with these three, there are maybe 15 other core subsystems of Postgres.

Over a couple of days I built a new database in Rust that architecturally had the same subsystems as Postgres. This step seemingly went very smooth. For each component, I already had a pretty good sense of how it should work. I gave Codex 5.4 access to the Postgres codebase and would ask it to come up with a plan for rewriting X subsystem of Postgres into pgrust-og. I would then review the plan and make sure it covered everything I wanted and would give Codex feedback on the plan where it fell short. From there I had codex execute the plan.

Given these were the core systems of Postgres, I read the code thoroughly to make sure I understood how they worked. This approach worked pretty well and after a couple of days I had knocked out pretty much all the core pieces.

Features, Features, Features

Once I had the core scaffolding in place, I started working on adding all the features that Postgres supports. The easiest way to do this was to look at the Postgres regression tests and look at all the features they were testing. Now the thing about Postgres is it has a surprising number of features. When it comes to features, Postgres looks almost like a programming language’s standard library. Postgres has:

Over 300 different types (including two different json types)

Nearly 500 different SQL keywords

More than 3000 different builtin functions

That’s a lot to implement!

Initially I was following the same approach I did when working on the foundation phase. The “problem” I was running into was that Codex was too good at implementing these features. For any individual feature, Codex is usually able to one-shot it. If you want to try it yourself, ask Codex to write a JSON parser for you. The problem I was running into was I would ask Codex to come up with a plan and then wait hours for it to implement the plan. I spent most of my time “programming” being idle!

This is when I realized that it might be possible to run multiple agents at a time. I decided it was time for a new approach. Instead of working on one feature at a time, I would try multiple. The next day I installed Conductor a tool that let’s you manage multiple agent sessions simultaneously. You can see the moment I started using Conductor in the git history:

Surprisingly, this approach worked! Because each feature was relatively independent of each other, multiple Codex agents could work on them independently. I eventually scaled up this approach and started spinning up as many as 20 agent sessions each. Usually I would look at which test files were left to work on and then spin up a session for each file. From there I would see what the current failures were and have Codex work on completing that file.

There were two issues with this approach. First I started burning through my Codex quota. I had to get multiple Codex accounts and switch between them in order to stay on the subscription plan. Second, I started maxing out CPU on my computer. Rust builds end up being somewhat cpu intensive and when you run enough builds, even my M4 Macbook Pro couldn’t handle them all. I ended up setting up GitHub actions, just so I could run tests off of my computer.

Last Mile

Over the course of about four weeks I was able to get 96% of the Postgres tests passing. That’s when progress started to slow down and things started to grind to a halt. The big obstacle came when I tried to get all the Postgres planner tests to work.

The postgres planner is the most complicated part of Postgres. It’s 50k lines of very nuanced logic that figures out the optimal way to fetch the data your SQL query is asking for. In short, it evaluates every possible way to fetch your rows out of the table, every possible way to perform the joins, and applies a advanced cost model to figure out the best way to plan the query. While pgrust-og had a planner and had all the functionality that postgres does, the way the planner was integrated into the rest of the codebase was subtly different. This led to an “organ transplant failure”.

To give an example of one of the failures, let me show you the differences in how pgrust-og and pgrust would represent a plan for the query: SELECT name FROM users WHERE age > 30. In Postgres this ends up being represented as a single plan node:

SeqScan { .scan.scanrelid = 1, .plan.targetlist = [ name ], .plan.qual = [ age > 30 ], }

While in Rust, it ended up being represented as three plan nodes:

Projection { .columns = [ name ], .input = Filter { .predicate = (age > 30), .input = SeqScan { .table = users, }, }, }

On top of that in Postgres the tableis referred to by an index for the query while in Rust it’s referred to by a string. While these look like small differences, they end up being massive. In C lots of functions will take a sequential scan node with a filter. In rust, those functions would sometimes need to take a sequential scan, sometimes take a filter node, and other times need to take a projection node. Fix just this one issue would be difficult as it would require rewriting everywhere where a seqscan, filter, or projection node is used.

In total, dozens of slight differences like this made it infeasible to get all the tests passing with pgrust-og. After struggling to get the planner to work I realized just how different the internals of pgrust-og were versus Postgres. If there were subtle differences in how the planner worked, who knew how many subtle differences there were in things like replication and backups. I realized it would be impossible to get pgrust-og into a production ready state. That’s when I decided it was time for a new approach. Enter c2rust.

cost: 8x codex accounts for 1 month = $1600

Attempt #2 – c2rust

For our next attempt we wanted to take a different approach. Instead of trying to go feature by feature, we wanted to see if there was some way we could transpile the Postgres code from C to Rust. That way each Rust code would match up line by line with equivalent Postgres code. It would be much easier to audit the code and show that I was doing things exactly the same way Postgres was doing.

c2rust is a open source project that will transpile your C code to unsafe rust. While that technically would be “Postgres rewritten in Rust” it wouldn’t help me further my goal of making it easy to add new features to Postgres. The idea was that we would use c2rust to unsafe rust and from there gradually rewrite the unsafe rust code into safe rust.

After toying with c2rust for two days, Jason managed to get it to completely transpile the Postgres C code to 5.3M lines of unsafe Rust. That resulting code completely passed the Postgres test suite and passed 100% of the Postgres regressions suite and had similar performance to Postgres. That’s not even the coolest part. The c2rust version of pgrust was ABI compatible with Postgres. That meant things like Postgres extensions would be compatible with Postgres. We didn’t even think that was possible!

At that point, we thought the hard part was over. Now all we had to do was have Codex refactor the code into idiomatic Rust. It turns out the hard part was not over.

When we tried to refactor the unsafe rust code, we found it would take hours to convert a single function. To show you why let me show you what some of the output of c2rust looks like:

pub unsafe extern "C" fn makeAlias( mut aliasname: *const ::core::ffi::c_char, mut colnames: *mut List, ) -> *mut Alias { let mut a: *mut Alias = newNode(::core::mem::size_of::() as size_t, T_Alias) as *mut Alias; (*a).aliasname = pstrdup(aliasname); (*a).colnames = colnames; return a; }

This looks closer to idiomatic C code than it does to idiomatic rust! Every value is represented as a pointer which more or less means all the code has to be unsafe. In order to convert a single function from unsafe rust to safe rust you had to change all the types the function accepted to be more idiomatic Rust types, change all the callers of the function, and change all the callees of the function. That meant changing one function could necessitate changing 100s of functions to make it idiomatic.

We tried a couple of different approaches. Could we define two versions of every function one that’s safe, one that’s unsafe? Could we make the internal functions of a package safe and leave the external functions unsafe? We were never able to get any of these incremental approaches to work that well. That’s when I had a new idea – what if instead of trying to rewrite the c2rust code incrementally, I instead created a new codebase and piece by piece, rewrote the c2rust code from unsafe Rust to idiomatic Rust. That led to the creation of pgrust-idiomatic.

Attempt #3 – pgrust-idiomatic

The output of c2rust was ~1000 individual Rust crates, with roughly one C file mapping to one Rust crate. The idea for pgrust-idiomatic was to rewrite the generated c2rust code, crate by crate. While I had considered doing a similar approach with the original Postgres code, I had brushed it off because it had seemed too high risk. If I’m rewriting it crate by crate, the code won’t work until I rewrite all of the crates. At the same time, Jarred Sumner had approached the infamous rewrite of Bun from Zig to Rust by going file by file. I figured if Jarred was successful with it, maybe I could be successful with it to.

What I started doing is asking my coding agent to identify a crate we could por

[truncated for AI cost control]