headshot of Ryan Ryan Marcus, assistant professor at the University of Pennsylvania (Fall '23). Using machine learning to build the next generation of data systems.
      
    ____                       __  ___                          
   / __ \__  ______ _____     /  |/  /___ _____________  _______
  / /_/ / / / / __ `/ __ \   / /|_/ / __ `/ ___/ ___/ / / / ___/
 / _, _/ /_/ / /_/ / / / /  / /  / / /_/ / /  / /__/ /_/ (__  ) 
/_/ |_|\__, /\__,_/_/ /_/  /_/  /_/\__,_/_/   \___/\__,_/____/  
      /____/                                                    
        
   ___                   __  ___                    
  / _ \__ _____ ____    /  |/  /__ ___________ _____
 / , _/ // / _ `/ _ \  / /|_/ / _ `/ __/ __/ // (_-<
/_/|_|\_, /\_,_/_//_/ /_/  /_/\_,_/_/  \__/\_,_/___/
     /___/                                          
        
   ___  __  ___                    
  / _ \/  |/  /__ ___________ _____
 / , _/ /|_/ / _ `/ __/ __/ // (_-<
/_/|_/_/  /_/\_,_/_/  \__/\_,_/___/                                   
        

Ten years of improvements in PostgreSQL's optimizer

As a query optimization researcher, I’ve spent the last 10 years of my life playing with, learning from, and building on top of the most sophisticated open source query optimizer out there, PostgreSQL. I recently wondered how much PostgreSQL had improved over the decade since I started working on databases. While changelogs and opinion pieces were plentiful, I couldn’t find any strong empirical comparisons, so I decided to run the join order benchmark (JOB)1 on PostgreSQL 8 through 16. I recorded the 90th percentile query latency for each database version.

Graph of P90 tail latency for different PostgreSQL versions. Speed improves drastically over time.

I built each version2 of PostgreSQL using GCC 13.2 inside a Docker container with Arch Linux. Since I wanted to measure the quality of the query optimizer, and not index/IO performance, I set shared_buffers to 8GB (large enough to hold the entire database). I also set work_mem to 8MB for all versions. Each query is executed once to warm the cache, then the median latency of 5 additional runs in recorded.

Overall, PostgreSQL’s tail performance has improved drastically, although versions 13 through 16 have been mostly stable. Comparing version 8 to version 16, PostgreSQL’s optimizer has dropped tail latency by nearly half in the last 10 years!

We can also investigate the entire query distribution (note the log scale):

Box plots of query latency for each major version. There is a slight slope downwards.

We can use regression analysis to (1) confirm that the downward slope in latency is significant, and (2) quantify how much improvement is brought by each version of PostgreSQL. If we regress the PostgreSQL major version number against query latency, we see that each new major version of PostgreSQL brings, on average, a 15% performance improvement on the Join Order Benchmark (). However, a linear model is arguably a poor measure of the change ().

Of course, not all of these improvements are attributable to the query optimizer. Improvements to the execution engine – from parallel workers to just-in-time (JIT) compilation – also play a role. It would be interesting to investigate how each query plan in JOB has changed over the year… maybe next time!

Quantifying the improvement aside:

You can also check out the raw data for yourself.

Notes

  1. The join order benchmark is a set of complex queries with many joins. The benchmark was introduced in the seminal paper “How Good are Query Optimizers, Really?”, in which the authors showcase the difficult nature of the join order benchmark. 

  2. I used the most recent minor version for each major version of PostgreSQL. For example, for PostgreSQL 8, I used version 8.4.22. These minor versions are often released after new major versions are available, but generally only contain bug fixes (not new features or performance improvements).