Optimization of NestLoop join in the case of guaranteed empty inner subtree
Hackorum builds and tests every patch posted to the lists, not only commitfest submissions. This is Hackorum's own CI rather than the PostgreSQL project's, and it is still under testing - please report anything that looks wrong.
You can run a PostgreSQL built from this patch straight from Docker, with no checkout and no build:
docker run --rm -p 5432:5432 ghcr.io/hackorum-dev/postgres-patch:t41652psql -h localhost -U postgresBuilt from patchset v3 (message #3), July 28, 2026 at 03:21 AM.
Every patchset is also pushed to a branch of our PostgreSQL fork, so you can check out the same tree CI built. Without a PostgreSQL checkout:
git clone --branch t41652_3 https://github.com/hackorum-dev/postgres.gitIn a checkout you already have, add the fork once:
git remote add hackorum https://github.com/hackorum-dev/postgres.gitthen, for this patchset and every later one:
git fetch hackorum t41652_3 && git checkout t41652_3Patchset v3 (message #3) is on t41652_3
During NestLoop execution we have bad corner case: if outer subtree
contains tuples the join node will scan inner subtree even if it does
not return any tuples.
To reproduce the problem see 'problem.sql' in attachment:
Out of explain analyze see in 'problem_explain.txt'
As you can see, executor scan each of 1e5 outer tuples despite the fact
that inner can't return any tuples.
Teodor Sigaev and I developed a patch to solve this problem. Result of
explain analyze procedure can be found in the 'optimized_execution.txt'.
--
Andrey Lepikhov
Postgres Professional
https://postgrespro.com
The Russian Postgres Company
Attachments:
problem_explain.txttext/plain; charset=UTF-8; name=problem_explain.txtDownload
0001-Skip-scan-of-outer-subtree-if-inner-of-the-NestedLoo.patchtext/x-patch; charset=UTF-8; name=0001-Skip-scan-of-outer-subtree-if-inner-of-the-NestedLoo.patchDownload+24-5
optimized_execution.txttext/plain; charset=UTF-8; name=optimized_execution.txtDownload
Andrey Lepikhov <a.lepikhov@postgrespro.ru> writes:
During NestLoop execution we have bad corner case: if outer subtree
contains tuples the join node will scan inner subtree even if it does
not return any tuples.
So the first question about corner-case optimizations like this is always
"how much overhead does it add in the normal case where it fails to gain
anything?". I see no performance numbers in your proposal.
I do not much like anything about the code, either: as written it's
only helpful for an especially narrow corner case (so narrow that
I wonder if it really ever helps at all: surely calling a nodeMaterial
whose tuplestore is empty doesn't cost much). But that doesn't stop it
from adding a bool to the generic PlanState struct, with global
implications. What I'd expected from your text description is that
nodeNestLoop would remember whether its inner child had returned zero rows
the first time, and assume that subsequent executions could be skipped
unless the inner child's parameters change.
regards, tom lane
On 12/11/19 8:49 PM, Tom Lane wrote:
Andrey Lepikhov <a.lepikhov@postgrespro.ru> writes:
During NestLoop execution we have bad corner case: if outer subtree
contains tuples the join node will scan inner subtree even if it does
not return any tuples.So the first question about corner-case optimizations like this is always
"how much overhead does it add in the normal case where it fails to gain
anything?". I see no performance numbers in your proposal.
I thought it is trivial. But quick study shows no differences that can
be seen.
I do not much like anything about the code, either: as written it's
only helpful for an especially narrow corner case (so narrow that
I wonder if it really ever helps at all: surely calling a nodeMaterial
whose tuplestore is empty doesn't cost much).
Scanning of large outer can be very costly. If you will try to play with
analytical queries you can find cases, where nested loops uses
materialization of zero tuples. At least one of the cases for this is
finding data gaps.
Also, this optimization exists in logic of hash join.
But that doesn't stop it
from adding a bool to the generic PlanState struct, with global
implications. What I'd expected from your text description is that
nodeNestLoop would remember whether its inner child had returned zero rows
the first time, and assume that subsequent executions could be skipped
unless the inner child's parameters change.
This note I was waiting for. I agree with you that adding a bool
variable to PlanState is excessful. See in attachment another version of
the optimization.
--
Andrey Lepikhov
Postgres Professional
https://postgrespro.com
The Russian Postgres Company