What’s up YouTube, today we’re going to propose my first major open source contribution.
Welcome to Postgres
If you’ve ever used a relational database you’ve heard of Postgres. It’s open source, highly flexible, actively maintained, and by golly it really works. A query in Postgres looks like a query in any other relational database:
SELECT display_name FROM users But if you want to do anything worth doing you’re going to use a WHERE clause.
SELECT display_name, email FROM users u
WHERE u.email LIKE '%@gmail.com'Ok now that you know everything there is to know about SQL let’s dive deep into the Postgres internals.
Indexing, and the query planner
Postgres has a lot of clever ways to store data. You have the option to specify indexes to add to different parts of that data, shipping 6 indexes by default 1. At C1 we mostly use B-Tree and GIN indexes. However, just because the indexes exist doesn’t mean they will be used - sometimes that’s good, sometimes that’s very, very bad.
When you submit a query to Postgres one of the processing steps it does before loading data is query planning. It takes your query and breaks it up into multiple chunks. The goal is to determine the most efficient way to load your data from the potentially multi-terrabyte sized cluster you have. For individual rows in a table, finding a few kilobytes of relevant data in that sort of pool is like finding a needle in a haystack, and Postgres can do it in milliseconds.
Plans in Postgres can be complex. I like a service provided by Dalibo to help visualize the information from a query plan. Dalibo has a “very large plan” as a sample query that you can look at here. Take a moment if you will to peruse the plan, you’ll see just how complex it can get within Postgres.
So here’s the key piece of information here:
Postgres chooses loading behavior largely based on estimated rows returned from the query
Consider this part of the plan from Dalibo:
The thing I want you to look at is actually not the red “Rows Removed by Join Filter”, it’s the under estimated by 370x. Both are bad, but they tell a different story. The rows removed tells you what happened with the data when the query was executed. The under estimate is actually indicative of how our planner thought it would look when the query was run. You can’t change the rows removed metrics. Using that condition, the same amount of rows will always be removed. What we want to do is reduce the number of rows Postgres ever has to consider in the first place.
To put it more concretely, if your condition is
WHERE users.department == "Engineering" AND name LIKE 'John %'the number of users not in engineering won’t change based on your plan. But if we can pre-bucket users by what department they’re in, we can prevent Postgres from even considering users from any other department. This loops it back to the Indexes I mentioned earlier.
Loading based on indexes is a two step process.
- First, we do a large exclusion based on a filter.
- Second, you actually load the data that the index is pointing to.
In our case, maybe an index on Department is something worth considering. Please note, I’m not advocating for adding indexes for any property you want to filter on. Indexes caused increased write load and often times your query is fast enough on more high-level filters that these unindexed filters aren’t a big deal.
Anyways, we’ve created our department index, and we want to do some better filtering. The query planner is going to look at the table statistics and make decisions on the shape. Let’s say even with the index and filters above, your table only has one user. It doesn’t make sense to do an index lookup, a sequential scan will always be faster. So when Postgres estimates your data to be very small, it could decide to always do a sequential scan. However, when you have 100k users in 20 different departments, doing the index filtering is clearly better.
That brings us to our next chapter
A bug in our query generator, and maybe Postgres?
There’s one last piece of the puzzle here I want to introduce before we continue. One of the things the query planner is responsible for is term deduplication. Consider the following query:
SELECT usernames FROM users u
WHERE u.deleted_at IS NULL AND u.tenant_id = 'logansprod'
AND u.deleted_at IS NULL AND u.tenant_id = 'logansprod'
AND u.deleted_at IS NULL AND u.tenant_id = 'logansprod'
AND u.deleted_at IS NULL AND u.tenant_id = 'logansprod'I know what you’re thinking, who could be so dumb as to write a query like this. Well, it was me, and I’ll tell you why. At C1 we want to setup our engineers to be able to consider only the business logic and not worry about accidentally making world-destroying mistakes. One such mistake would be accidentally showing customer A data from customer B. As a AI, Security, and otherwise well-intentioned company it’s important that we reduce as many possibilities of these issues as we can. In our primary database DynamoDB, every object has the tenant_id as part of the primary key. This makes it IMPOSSIBLE to load data from one customer and another customer in the same query. In Postgres though, we have no such guarantees.
So we built a lightweight ORM. It’s a compile-time safe way to write Golang that at runtime becomes valid SQL while also ensuring that every WHERE clause, JOIN, or sub-select only ever happens for the single tenant_id for the customer we’re looking at. The good news is, that was never an issue. However, due to, well, lazyness, we were fine with the queries being generated as above. “It’s fine,” we said, “Postgres will dedupe the clauses anyways,” we thought. Well… we were half right :)
One of the indexes we add to every table is on deleted_at. It just makes sense, most of the time we’re loading data from non-deleted objects, including IS NULL in the query to make sure that’s the case. We do the same for tenant_id, because we are always filtering on TenantID. And where we were right is this: The TenantID filter does indeed get deduplicated from a query that looks like this. But then we saw this and got a bit scared.
17 seconds? Underestimated by thirty-three THOUSAND, what the hell is going on here?
Credit where credit is due, the key breakthrough here actually came from Anthropic’s Fable 5. The suggestion was a simple one: “What if you remove the duplicate where clauses, does the performance improve?” It’s so simple in fact we nearly dismissed it because surely the Postgres query planner does this correctly.
So it turns out IS [NOT] NULL is actually uniquely different. Instead of a general equality filter, NULL checks do something different. For the table, or index, it checks the null_frac and applies a reduction to the planned number of rows based on that null frac in either direction. If the IS NULL checks were deduplicated it wouldn’t be an issue, that’s working as intended, and that’s the root cause of our problem here. When this null_frac is applied it is applied exponentially. Every additional IS NULL reduces the estimate by the null_frac, so if your null fraction is 10%, just three IS NULL clauses reduce it by 1000x, and as you may be able to guess we had more than three IS NULL clauses. This reduction is applied in clausesel.c.
So we’ve done it you and I, we found the bug. The estimates are significantly wrong for anything where we apply copious IS NULL checks. That’s not so great. Unfortunately, this wreaks havoc on the query planner. That 33k underestimate is caused by the problem above. If Postgres thinks that you want to load 7 rows, but actually has to load 230k sequentially, we’re doing much much more work than anticipated. Ultimately, since the planner decides how we load the data, being this wrong just ruins any query with this sort of data shape.
The entirety of the previous query took 50 seconds (give or take) to execute. That’s unacceptable. Anything over 15 seconds we kill at the edge layer anyways, so these queries just never worked for that particular customer. With the patched version of the query generated that went down to 293 milliseconds. That is a 170x reduction in query execution time just by fixing the broken query generation. I don’t even have a like-for-like screenshot of the plan node for you because the query plan was so different it didn’t even scan the app_entitlements table despite that being part of the query itself.
My 2c, Postgres should patch this footgun. Yes, our query planner was insane and lazy, and for that I apologize. But in the wise words of my coworker Dan, if you’re going to propose someone should do something, you do it. So anyways, here’s the email I wrote to pqsql-hackers with a patch, and an easy way to view it in github.
Also worth noting if you want to double-check my reproduction case I made a test repository here.
As always, this post was written by hand.