Forcing Join Order in Postgres Using Optimization Barriers
In today’s episode 67 of “5mins of Postgres” I want to talk about forcing join order in Postgres. We’ll walk through 3 techniques: Adding OFFSET “0” to a sub-SELECT, using common table expressions, and working with the join_collapse_limit.
Let's have a look!
This is a blog post by Laurenz Albe on the Cybertec blog, where he talks about how you can force the Postgres query planner to join tables in a particular order. This is oftentimes a useful technique when you are trying to understand why the planner made a certain choice, and if there's a better query plan available that, for example, could use an index in a parameterized index scan.
First of all, Laurenz takes an example of a JOIN between three tables, "a", "b", and "c". By default, Postgres decides to
- do a sequential scan on "b"
- then do a Nested Loop Join and
- use the outputs from the sequential scan on "b" to do a parametrized index scan on "a".
There's a reason why Postgres chose the query plan this way, because the costs ultimately were the lowest, with this approach.
However, oftentimes this can be incorrect. For example, one thing I've noticed myself is that Memoize in Postgres 14 does tend to influence plans quite aggressively because it makes the inner side of the nested loop join very cheap. In order to understand those planner choices we want to try alternate join orders, but how can we get Postgres to produce a different query plan with a different join order?
Memoize in Postgres 14 does tend to influence plans quite aggressively because it makes the inner side of the nested loop join very cheap.
Laurenz describes the basic technique, which is that you would write a subquery, a sub-select, and then force Postgres to not pull up the subquery. By default, when you write something as a sub-select, Postgres will ignore the fact that you wrote that as a sub-select, and it will just pull this up and try to plan things at the same level.
This feature is called subquery pull-up and is generally a good feature that you want to have. However, the problem here is that it does allow Postgres to rearrange the join order and so it disregards the fact that you put it down into the sub-select. We can prevent Postgres from doing this.
The first technique that Laurenz mentions here is using
OFFSET 0. When you add
OFFSET 0 to a sub-SELECT like this, it essentially acts as what's called an optimization barrier. This prevents Postgres from doing the subquery pull-up and through that method then makes sure that "b" and "c" are joined together first, and then afterwards we join against "a".
Compared to the first query plan, now we're actually getting a hash join between "c" and "b", and only afterwards are we getting an index scan on "a".
An alternate way of doing this is using common table expressions. Starting in Postgres 12, you can define whether a CTE should be materialized or not, or you want to leave the choice up to the Postgres planner. If you add the
MATERIALIZED keyword, Postgres will treat the CTE as an optimization barrier, and will not do the subquery pull-up with the CTE query. This doesn't actually produce the same plan as with the "OFFSET 0" trick. Postgres has a few mechanisms of how it considers CTEs differently than actual subqueries, and so I would probably prefer to use "OFFSET 0" instead of a CTE.
There's a third technique: Postgres has a setting called
join_collapse_limit. The join collapse limit helps Postgres handle situations where you have a lot of tables.
By default, when you join more than 12 tables together, Postgres comes up with ways of avoiding an exhaustive search for the optimal join order. Once you hit 12, Postgres by default would switch to what's called the genetic query optimizer. The genetic query optimizer is a trade-off of saying I'm okay with a non-ideal join order because it's actually better to reach a planning decision faster and have that be non-deterministic.
There is an interesting trick here, where we keep the
geqo_threshold at 12, so we don't engage the genetic query optimizer, but we reduce the
join_collapse_limit. What that means is that we're now actually relying on the order of how the tables are written in the query.
In Laurenz’ example case, because we first do "FROM b" and then "JOIN c" and then "JOIN a" we're telling Postgres to first join "b" and "c" and then join "a". It's essentially following what the query text is instead of making up its own mind. This then leads to the same query plan as we got when we had
OFFSET 0 in the sub-SELECT.
At the end of Laurenz post, you can see that Franck had an interesting comment. All of the techniques discussed here force the join order, but they don't force the join direction. The only way to do that today is to use pg_hint_plan.
pg_hint_plan is an extension for Postgres that you would have to install or enable on your cloud provider platform.
With pg_hint_plan, we add a special comment to tell it what shape the plan should have. We can define the join order using the "Leading" query hint. The Leading query hint can define join order, but it can also define join direction. In this case here, we first tell it to join "t2" and "t3" and then we join the result of that with "t1". We're also telling it to first scan "t2" and then scan "t3". In this case, "t2" is what's called the outer table and "t3" is called the inner table. In nested loop joins, you could only do a parameterized index scan on the inner table. If you flipped around the order, that will most certainly give you different results if you're relying on parameterized index scans.
If you're interested in this topic, I hosted a webinar a couple of weeks back where we talked about the importance of join order, as well as a few other Postgres planner optimization techniques. You can find the link to the webinar in the description of the YouTube video.