Faster query plans with Postgres 16: Incremental Sorts, Anti-JOINs and more
In today’s E101 of “5mins of Postgres” we talk about the planner improvements in Postgres 16, including better use of Incremental Sort, more efficient anti-JOINs, Hash Join improvements, more efficient window functions, and more. And all of that without having to change your queries!
Share this episode: Click here to share this episode on LinkedIn or on X/Twitter. Feel free to sign up for our newsletter and subscribe to our YouTube channel.
Transcript
In this blog post by David Rowley on the Citus Data blog, David describes some of his own work in Postgres 16, as well as the work of other people in the Postgres community. David knows what he's talking about since he's been one of the main contributors to planner improvements in Postgres 16.
Now, this is a long post - there's 10 different improvements that David lists, but I'm going to try to cover this quickly and I'm also going to editorialize the order here a little bit, to make this easier to digest. We won't go through these in order, but rather I have four different categories of changes that we can talk about.
If you want to see EXPLAIN plans for each of these, David went through a lot of effort to put examples together for each improvement - you can find direct links to the relevant part of the original article via the "full details" links below.
Reuse the existing sort order more often
In Postgres, there's a concept called Incremental Sorts. This is something that has existed since Postgres 13. The idea behind incremental sorts is that if you are already getting sorted data, for example, from a B-tree index, you can avoid a lot of unnecessary work by having Postgres only incrementally sort for the extra sorting that needs to be done.
For example, you're querying for two columns, "a" and "b". You have an index on column "a", and.so Postgres only needs to do the sorting for column "b", saving a lot of work.
Incremental sorts for DISTINCT queries (full details)
Now the change here in Postgres 16, is that when you have a SELECT DISTINCT, Postgres will be able to also do an incremental sort. When we look at the query plan here, this is very obvious.
So if you see this improvement, what you would expect in terms of plan change, is that now in 16, you'll see this Incremental Sort node on your SELECT DISTINCT query. And this will very likely improve query performance, in this example, almost a 2x improvement.
Faster ORDER BY / DISTINCT aggregates (full details)
Another improvement that relates to sorted data is that aggregates that have an ORDER BY or DISTINCT clause in them are now able to use pre-sorted data. In this example, we have an index on "a" and "b" and we're first grouping by "a" and in the SELECT we're counting the number of distinct "b"s. And so previously in Postgres 15, this would have had to do a sort, and this sort is kind of hard to see in your explain plan, but you can know about this here when you look at the temp file "read" and "written". This means what Postgres was doing is it got all that data back and it did an additional sort in order to implement that DISTINCT inside the count. In Postgres 16 however, that effort is gone and because sorting on disk is expensive we can see that there's about a 3x improvement here going from 15 to 16.
Incremental Sort after Merge Join, in more cases (full details)
Now, third, in the context of sorting. There's a change that relates to the planner doing Merge Join.
Merge joins work with sorted data. And so having a better understanding of incremental sorts in the merge join logic, it's actually very helpful. And so this is a bit more complex example. You can also see that David explicitly turns off hash joins and parallel query to show this example. And so we can see that in Postgres 15, Postgres did a Merge Join and on top of the Merge Join, sorted that output. Versus in Postgres 16, Postgres is able to reuse the fact that the Merge Join output already has a particular sort order, and so can do an incremental sort on top of the Merge Join.
Here this is just a very small improvement, but I'm sure if you do joins with large amounts of data, this could have a nice benefit.
Now, let's talk a bit more about joins.
JOIN improvements
Support Right Anti Join (full details)
Another improvement here is related to anti-joins. An anti-join usually happens when you use a NOT EXISTS clause in your query. Now, the implementation here has become a bit more flexible in Postgres 16 with the addition of "Right Anti Join".
This matters, because in the case of a Hash Join, Postgres will build a hash table on one of the two tables being joined. And Postgres generally prefers to do this on the smaller table because that's going to be more efficient. But the problem is that previously, in older releases, it always built the hash table on the table referenced inside that NOT EXISTS. And so in Postgres 16, Postgres can now do either or by using a right anti-join. And so what you would see happen, if Postgres makes a different choice here, is that instead of seeing a "Hash Anti Join", you would now see a "Hash Right Anti Join". And you would see the join order of tables change. In this case, it's almost a 2x improvement in query runtime.
Parallel Hash Full and Right Joins (full details)
Now, talking about Hash Joins: Since Postgres 11 we have the benefit of parallel hash joins. This means that Postgres will use parallel workers to build a hash table that's shared between the different backends. And this can sometimes you know be quite a significant performance improvement.
And so in Postgres 16 parallel hash join now supports full and right joins. This means, previously in Postgres 15, this would not have allowed the Hash Join to be inside of the parallel part of the query plan, but now we can actually see, that we have a Parallel Hash Full Join that encompasses both of the Parallel Sequential Scans.
JOIN removals for partitioned tables (full details)
Now last, on the note of joins: Sometimes you join things, but you don't actually need the data. For example, ORMs might unnecessarily join data that's not needed. And so Postgres is now smarter about this. When you left join a table, but you're not actually using that table, Postgres will now be able to actually remove this.
Here in this example, Postgres previously, did a whole bunch of work for nothing really, versus in Postgres 16 it's able to detect that it just needs to do a simple sequential scan on the table. This is very situational, but sometimes when you have bad queries that you don't even know about maybe, this will save a little bit of time.
Now, we're almost finished.
Speed-ups for window functions
Optimize window function frame clauses (full details)
The first one, again, relates to how you write your queries. When you write a window function, there is essentially a slower way and a faster way for Postgres to work on these functions.
And this relates to what's either called the ROWS or the RANGE mode. Many times we don't really think about this. We might write something simple, like "row_number() OVER", and then a certain ORDER. And so Postgres previously would do unnecessary work.
And so Postgres 15 in this example would end up doing a lot more work, fetching a lot more rows, in this case 50,000 rows, versus in Postgres 16, Postgres knows that it can actually terminate this window function early as it only needs to fetch 11 rows.
Optimize various window functions (full details)
Another improvement related to window functions is also related to not doing unnecessary work.
And so in this case, this relates to certain types of window functions. This behavior already existed for functions like "count" or "rank" or "row_number". But now in Postgres 16, if you're using functions like "ntile", "cume_dist" or "percent_rank", these can now benefit from that same early termination of the window function.
And so you can see here on Postgres 15, the WindowAgg node returned 50,000 rows, only to throw away most of them right afterwards. Versus in Postgres 16, Postgres can finish early and only process 500 rows.
And again, of course, significant performance improvement, in this case about a 4x difference.
Oh, and there are two more things..
Now last there's two things that are kind of unrelated to everything we've talked about so far.
Memoize for UNION ALL queries (full details)
The first one relates to Memoize. Memoize is essentially a way for Postgres to avoid repeated work. And I've been on both sides of the coin of finding Memoize useful or not useful, I've definitely seen plans where it caused some odd behavior, but generally speaking, it's a good performance improvement.
And so now in Postgres 16, Memoize can also be used when there's a UNION ALL involved. So in this case you can see, we have two tables being unioned together, and then they're being joined to a third table. Now in Postgres 15, this query took 2000 milliseconds. In Postgres 16, it's down to a nice 280 milliseconds. The reason that is possible is because Postgres can memorize some of the values. And so it saves repeated work of having to look up the same data all over again in the Nested Loop.
Short circuit trivial DISTINCT queries (full details)
And now last, another situational improvement. What this here does, is it avoids having to do the work of making the results unique if Postgres has other means of detecting this uniqueness. In this case, we are looking for three columns, "a", "b" and "c", and we're also returning the result as DISTINCT on all these 3 columns we're looking for.
And just by virtue of us looking up these fixed values, we know that the result of that scan is already going to be unique. So in Postgres 15, Postgres would unnecessarily do a Unique node here. Versus in Postgres 16, Postgres is correctly able to say, "as soon as I have a result, I'm good. I'm done". This can be a very nice improvement, if you have queries written this way.
In conclusion
A lot of engineering work was done to get all of this into Postgres 16, and this is really a collaborative effort.
Over the many years that Postgres has improved it's planner, it's definitely shown that change is slow in the Postgres query planner, but that also means that we can usually trust new Postgres releases to be pretty stable in terms of plans. That means when we upgrade, we would usually see an improvement or at least the plan to stay stable between the releases.
I'm excited to upgrade to Postgres 16, to get these improvements. And I would encourage you to try them out. They're all enabled by default, so all you have to do is look at your query plan with EXPLAIN ANALYZE, or auto_explain, and see these benefits for your workload.
I hope you learned something new from E101 of 5mins of Postgres. Feel free to subscribe to our YouTube channel, sign up for our newsletter or follow us on LinkedIn and X/Twitter to get updates about new episodes!