Ten years of improvements in PostgreSQL's optimizer

Yeah pg’s JIT is a pretty good demonstration that LLVM is not great at JITs, worsened by postgres not having a good persistent shared query cache.

It would probably be less detrimental if it could perform asynchronous compilation for future queries (which really is closer to how normal JITs actually behave, at least for optimising backends)

The JIT compiler is great for analytical queries.

You can configure thresholds for the JIT activation in PostgreSQL as well if you want to elevate the bar from which the JIT is enabled.

Can't postgres JIT a query once and run the compiled query multiple times?

A customer had the worst performance issues after switching to postgres. Weirdly it only happened in the docker and test server setup and not on the developers machine (he ran postgres via homebrew).

Turns out homebrew installed postgres without JIT support and one query on the developer machine ran in 200ms, while with JIT the query took 4-5 seconds. Took some time to figure out, since I'm not a heavy postgres user, but since then I've always disabled JIT and never looked back.

It describes all the way the SQL could be executed, then choses the faster plan. For example: if you're looking for the user row with user_id xx, do you read the full table then filter it (you have to look at all the rows)? Or do you use the dedicated data structure to do so (an index will enable to do it in the logarithm of the number of rows)?

A lot more can be done: choosing the join order, choosing the join strategies, pushing the filter predicates at the source, etc. That's the vast topic of SQL optimization.

For the databases I've used, which excludes PostgreSQL, most optimization happens on algorithmic level, that is, selecting the best algorithms to use for a given query and in what order to execute them.

From what I gather this is mostly because various different SQL queries might get transformed into the same "instructions", or execution plan, but also because SQL semantics doesn't leave much room for language-level optimizations.

As a sibling comment noted, an important decision is if you can replace a full table scan with an index lookup or index scan instead.

For example, if you need to do a full table scan, and do significant computation per row to determine if a row should be included in the result set, the optimizer might change the full table scan with a parallel table scan then merge the results from each parallel task.

When writing performant code for a compiler, you'll want to know how your compilers optimizer transforms the source code to machine instructions, so you prefer writing code the optimizer handles well and avoid writing code the optimizer outputs slower machine instructions for. After all the optimizer is programmed to detect certain patterns and transform them.

Same thing with a query optimizer and its execution plan. You'll have to learn which patterns the query optimizer in the database you're using can handle and generate efficient execution plans for.

The query optimization chooses what algorithms provide the results requested by the SQL.

At a very high level, the query planner's goal is to minimize the cost of reading data from disk. It gathers pre-computed column statistics, like counts of rows and distinct values, to estimate the number of rows a query is likely to match. It uses this information to order joins and choose indexes, among other things. Joins can be accomplished with several different algorithms, like hashing or looping or merging. The cheapest option depends on factors like whether one side fits in working memory or whether both sides are already sorted, e.g. thanks to index scans.

I'm curious to hear a bit more of your opinion. For example, I'm surprised that syscall latency is something near the top of your list. I think the usual wisdom in the DB community is that the cost models are mostly fine, but the cardinality estimation is really bad.

In terms of the deferred / alternative planning, do you think adaptive query execution is a reasonable way to achieve this? It certainly allows for information early in the query execution to impact later plans. My worry with these approaches is that if you get the first couple of joins wrong (which is not uncommon), unless you have something like Yannakakis/SIPs, you still can't recover.

I am obviously biased on the whole "ML for query optimization" thing. One thing I would note is that every "ML for planning" approach I've seen does, under the hood, use ML for cost discovery/estimation. These approaches are just trying to balance the data they collect (exploration) with the quality of the plans they produce (exploitation). Interestingly, if you use ML in a way that is completely removed from planning, you actually get worse query plans despite more accurate estimates: https://people.csail.mit.edu/tatbul/publications/flowloss_vl... (again, I've got a horse in this race, so my opinion should come with a side of salt :D)

Another omission is foreign key statistics. Joins along foreign keys should never have a bad plan, but they still occasionally do.

I'm curious what you mean. Postres, like many RDBMSs, does not automatically create an index on a FK. But you have to know that already.

Is it join sequencing?

Deferred or alternative scenario planning should be adopted, especially for large and expensive queries. As it is today, your plan is finalized before it is executed, even though earlier stages of execution could provide information (like rowcounts or cardinality estimates) that could dramatically improve later stage plans.

Alternative planning sounds awesome. I saw a query plan the other day where it expected about 1000 rows from some subquery so did a nested loop to an index scan. In reality there’s about a billion rows. I’m not sure yet why the estimate was so bad, but being able to pivot from a nested loop to a hash join if the row count crossed some threshold would be great at avoiding some catastrophic plans.

Do you think that MSSQL is better on this front?

The nice thing about compiler optimizations is that you can improve performance of existing CPU's without physically touching them. Year by year. You squeeze more of the machine someone designed. It adds up.

Imagine what environmental impact you would have if you optimized Python's performance by 1%? How much CO2 are you removing from the atmosphere? It's likely to overshadow the environmental footprint of you, your family and all your friends combined. Hell, maybe it's the entire city you live in. All because someone spent time implementing a few bitwise tricks.

That seems like a very weak “law”. Is it meant as a joke? The supporting evidence is just numbers pulled apparently from nowhere (“let’s assume…”) and the conclusion is wildly off base. They seem to imply that if optimization improves the performance of much of the world’s software, by 4% each year, then it’s a waste of time.

Murphy’s law is the only comparison given. I wonder what the comparative expense is to develop faster and faster hardware, vs. to keep improving compilers. Depending on how the ROIs compare, (in dollars-per-percent gain, let’s say) maybe this “law” is worth some weight.

OTOH, the Postgres article in question seems to show diminishing returns from optimization, which belies the whole premise of the “law” which assumes the gain is consistent from year to year. And might prove Prorbstig’s implied point about optimization being a bad investment over the long term!

Why? The at law seems to talk about how performance software improvements isn’t relevant while this article talks about how there improvements to Postgres has been significant.

Is it because you view the 15% to be a low number? Because it really, really, isn’t in the context. It’s certainly smaller than the 60% from your linked law especially if you do the whole 15/10 thing, but you really shouldn’t compare Postgres’s performance to hardware increases because they aren’t the same. You would need absolutely massive amounts of hardware improvements to compare to even 1% performance on what is being measured here.

I don’t think the law is as silly as other posters here, but it’s talking about programming language compile times. I wouldn’t compare something as unimportant as that to what is arguably one of the most important things in computer science… considering how much data storage and consumption means to our world.

In this case, the researcher built each PostgreSQL version using the same GCC version (13.2) and tested on the same OS.

But at least they maintained the courtesy of major version filesystem compatibility allowing faster in-place upgrades during an extended period (from v9.0 - 9.6), by simply changing the binaries. Possibly that held them back, but yearly updates that require more downtime/reindexing isn't so much fun, and possibly the reason why many sites skip upgrades until previous versions drop out of support (esp AWS RDS users). While the alternative of a logical replication upgrade (from v10 onward) has availability benefits, its a major project with unavoidable costs and significant risks unless schemas are relatively simple.

I totally agree -- I picked the latest version for each major version using the semver interpretation of the version numbers, which is not how PostgreSQL has traditionally done major version numbers (i.e., PG 8.2 and 8.1 are different major versions, but I interpreted the version numbers as if they were minor versions).

The main reason I did this was to reduce the number of versions I had to test, but I agree a more complete analysis would test each (true) major version.

It is certainly possible that the plans are similar, and that improvements to the execution engine are being measured. The join order benchmark was designed to test optimizer quality. It is worth noting that in addition to trying to measure the number of pages read from disk, the PG optimizer also tries to reduce the number of tuples examined by the CPU, the number of predicate evaluations, etc. All these numbers are rolled up into a "cost," which is the function that the optimizer minimizes.

It is also true that measuring cold cache and warm cache performance can produce different results, and this experiment is certainly in the warm cache scenario. But, the cold cache scenario suffers from the problem you mention as well: an improvement to PG's B-tree that saves a few IOs will dominate any kind of CPU-based improvement (at least at the data size of the join order benchmark).

FWIW, the plan for the query with the P90 latency changes from a plan that uses loop and merge join in PG8.4 to a plan that uses hash join in PG16 (where it is no longer the P90 query), which is at least some evidence of optimizer improvements.

No, it optimizes cost, which includes pages read from disk _and_ things like CPU use. Cost is an arbitrary unit meant to correlate with time spent, not by disk loads, so it's completely reasonable to compare plans with everything loaded in RAM. (Cost is by convention scaled such that one page read from disk is 1.0, but that's a different things from “the optimizer will try to minimize the number of pages read from disk”. It could just as well have been scaled so that 1.0 was 1 ms on some arbitrary machine.)

I'm the author of the blog post.

"Tail latency has improved by YMMV for everything else" => yes, I think that's a valid (but conservative) read. Of course, in many (most?) applications, tail latency is very important. Tail latency also tends to be the thing that optimizer engineers target (i.e., reduce the runtime of the longest running query).