5mins of Postgres E19: Speeding up sort performance in Postgres 15

By Lukas Fittl

May 26, 2022

Today, we're going to talk about four specific improvements made in Postgres 15 that help speeding up sort performance:

Sorting a single column
Reducing memory consumption by using a different memory allocator
New specialized sort routines for common data types
Replacing the algorithm that's used for splitting up sorts to disk when they exceed the "work_mem".

Share this episode: Click here to share this episode on twitter, or sign up for our newsletter and check out the newsletter archive and subscribe to our YouTube channel.

Four improvements that help speeding up sort performance in Postgres 15
What we have discussed in this episode of 5mins of Postgres

Transcript

Let's have a look!

Four improvements that help speeding up sort performance in Postgres 15

In this blog post by David Rowley, he talks about the improvements that were made to the Postgres 15 release in regards to sorting. This is work that was done by him and three other authors, Ronan, Thomas and Heikki.

Why does sort performance matter? Sorting is not just happening in ORDER BY queries, but sorts are also relevant for aggregate functions, for GROUP BY queries, UNION, or DISTINCT, or having a WINDOW function. There's a lot of things where sorting matters and Postgres will be faster in Postgres 15, thanks to these changes.

There are four improvements in this post that we're going to go through today.

1. Special casing single single column sorts in Postgres 15

The first improvement is on sorting a single column. The simplest example here is SELECT col1 FROM table ORDER BY col1.

In previous Postgres versions what Postgres will do is, even in simple sorts like this, it will work with the whole row that was retrieved from the table. In Postgres 15 on the other hand, that is special cased, and so single column sorts are significantly faster. This only applies to single columns, so if you have two columns, for example, then that keeps using the same row based approach as before.

This also applies to cases that do merge semi or anti joins. Most typical case for this would be an EXISTS clause, I'm sure you've written queries that used those before. The performance improvement here is actually quite impressive! For sorting 10,000 integer values and sorting a single column, in Postgres 14 that takes 1.8 milliseconds and in Postgres 15 it takes 1.49 milliseconds. So that is about 26% improvement.

2. Reducing memory consumption to speed up sorts in Postgres 15

The second change that was made is reducing memory consumption by using a different memory allocator. Postgres has two main memory allocators that are relevant here, the first is the "aset" memory allocator. When "aset" ends up making a memory allocation, it allocates that in the power of two. It helps avoid a lot of small allocations, which can be expensive.

The other aspect here is that, when memory is freed, Postgres is able to reuse that memory better with the "aset" allocator. The most important realization here was that typically, Postgres doesn't actually need to free memory for records when sorting. Because it knows how big the sort is, it loads all the data, it does the sorting, and at the end, when the sort is complete, it frees the data. So that's a bad fit for the default allocator.

The other allocator is the "generation" allocator in Postgres. It doesn't have some of the overhead of the "aset" allocator and it doesn't have that same power of two behavior. This shows between a 3% and a 44% improvement.

This doesn't apply for what's called a "bounded" sort. A bounded sort is when you have an ORDER BY and a LIMIT clause. What's special about those types of sorts is that Postgres actually does free memory after it got enough data after the limit is reached, because of that it's actually better to use the "aset" allocator.

3. New specialized sort routines for common data types

The third improvement is new specialized sort routines for common data types. Postgres has customizable data types, you can create your own datatypes, write some C code, Postgres is very flexible in that regard.

That flexibility has a downside, when Postgres does a sort, it has to call into a data type specific function, to do comparisons. As part of its quicksort algorithm, it has to do a comparison and say, is this larger, is this smaller, is this the same?

David ran the numbers here, if you're sorting 10,000 records, that comparison function has to be called about 132,000 times. If you're sorting 1 million records it has to be called 20 million times!

Obviously, there's a lot of function calls here. C compilers can inline things, but depending on the level of indirection, that inlining doesn't always happen. The change here is that there are new special functions for built-in data types that speed up the function call by inlining things.

These functions have been added for

integer types
timestamps
and also if you're using a text type with a C collation.

That gives a nice, consistent improvement, between 4 to 6%. You don't need to do any extra work, if you use the standard datatypes, then this improves the performance.

4. Replacing the algorithm that's used for splitting up sorts to disk when they exceed the "work_mem".

Last but not least, there was also an improvement if your sort spills to disk a lot. This improvement here replaces the algorithm that's used for splitting up sorts to disk when they exceed the "work_mem".

"work_mem" controls at which point a sort is on disk versus in memory. The main benefit of this change is that it uses less I/O for it during the sort. For example, if you have a four megabyte "work_mem", and you're sorting a 10 gigabyte table, on Postgres 14 that took 60 seconds. On Postgres 15, it only takes 43 seconds. That's quite impressive improvements here.

If you want to try out Postgres 15, you can try out the beta1 today!

The other thing I want to mention here is that if you're interested in learning more about new Postgres features and what the Postgres community is working on: Currently, this is end of May, 2022, PGCon is happening. PGCon is the main Postgres hacker conference that happens once a year, typically in Ottawa, but this year again, it's online.

Now is a great time to listen in and learn more about how Postgres works internally.

Thank you so much for listening. This was 5mins of Postgres, subscribe to our YouTube channel and follow us on Twitter to hear about next week's episode and talk to you next week.