Plan a filtering inner join as a semijoin
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:t253553psql -h localhost -U postgresBuilt from patchset v1 (message #1), August 28, 2026 at 03:40 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 t253553_1 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 t253553_1 && git checkout t253553_1Patchset v1 (message #1) is on t253553_1
Hey hackers,
Recently I improved a dynamic SQL compiler (an ORM-like layer) using a
pattern that seems to generalize to the Postgres planner. I taught the
layer to emit an EXISTS subquery when the target relation only served to
filter, rather than fanning out a join whose extra rows were discarded.
That led me into the join elimination machinery, and to the attached draft
patch. It adds convert_joins_to_semijoins(), which recognizes an inner
join that only restricts which rows survive and adds a JOIN_SEMI
SpecialJoinInfo for the filtering relation. Two conditions must hold: the
query must discard duplicates, and nothing outside the join clauses may
reference the relation.
The patch works, but only by being narrowed to the point where most of the
idea goes uncaptured.
Results: enable_semijoin_conversion off versus on, same data, serial
plans, work_mem 4MB, median of 5 runs. 100,000 posts and 10,000 authors;
fanout is the number of matching righthand rows per driver row, so it is
exactly the number of duplicate rows the join produces and the dedup step
removes. Fanout =1 is the control.
query fanout =1 =2 =8 =32
--------------------------------------------------------------
DISTINCT over a to-many join 0.98x 1.14x 4.64x 9.42x
count(DISTINCT) over a to-many 0.98x 0.93x 2.75x 11.06x
GROUP BY with max() 1.01x 1.17x 2.33x 6.99x
DISTINCT, driver also filtered 0.92x 1.19x 1.33x 6.87x
The patch lifts one relation at a time. The righthand side must be a single relation;
a chain is declined outright. (I discovered that LHS selectivity trumps row
multiplicativity when there is no index to probe). This forced me to bind the RHS
and forgo most of the upside.
From the same run, at fanout 32:
SELECT a.id, a.name, a.country FROM author a
WHERE EXISTS (SELECT 1
FROM post p JOIN comment c ON c.post_id = p.id
WHERE p.author_id = a.id AND c.spam
);
Master 4527ms
hand-written EXISTS 104ms 43.6x
Which brings me to the layering question. The neighboring machinery here increases
planner freedom: join elimination removes a relation the query can't observe, self-join
elimination removes a redundant one; etc. My patch (currently) decreases it.
My intent now is to follow the eager aggregation work and build at a lower layer.
Rather than replacing joins, offer the planner an alternative to choose on cost. Concretely,
a parallel "distinct relation", holding rows made distinct on the columns the query can
observe, carried through the join search, competing on cost, with no SpecialJoinInfo
and no order constraint.
One caveat: Reaching the ceiling will certainly require existence semantics and an
index-driven exit. So a distinct relation would have to be able to source a semijoin path
(not just a pre-deduplicated one). And I wonder whether that can be expressed without
reintroducing the join-order/selectivity constraint?
Patch attached; it applies to master today.
Thanks,
Will
Attachments:
t253553_10002-semijoin-v1-patch-b.patchapplication/octet-stream; name=0002-semijoin-v1-patch-b.patchDownload+1014-1
0003-semijoin-v1-patch-c.patchapplication/octet-stream; name=0003-semijoin-v1-patch-c.patchDownload+684-6
0004-semijoin-v1-patch-d.patchapplication/octet-stream; name=0004-semijoin-v1-patch-d.patchDownload+207-0
0001-semijoin-v1-patch-a.patchapplication/octet-stream; name=0001-semijoin-v1-patch-a.patchDownload+3-3
William Bernbaum <wbernbaum@dwdev.com> writes:
Recently I improved a dynamic SQL compiler (an ORM-like layer) using a
pattern that seems to generalize to the Postgres planner. I taught the
layer to emit an EXISTS subquery when the target relation only served to
filter, rather than fanning out a join whose extra rows were discarded.
That led me into the join elimination machinery, and to the attached draft
patch. It adds convert_joins_to_semijoins(), which recognizes an inner
join that only restricts which rows survive and adds a JOIN_SEMI
SpecialJoinInfo for the filtering relation.
I find myself a bit astonished by this proposal. Normally we try
to convert semijoins to inner joins in order to gain join-order
flexibility. I can't see a good reason to go in the other direction.
There might be a reason to install some special case for the query
pattern you have in mind, but I really doubt that this particular
special case is the best option.
regards, tom lane
Tom,
Fair; completely agreed. In my initial testing, I couldn't overcome a case where pinning a filter rel to the RHS deferred a qual that should have been first. And the selectivity (surely obvious to some; not to me) outweighed any row reduction benefit.
That's why I narrowed it to a single-relation RHS (and gave up the prize - the measured hand-written EXISTS).
One clarification.. not a defense. This isn't quite the reverse of reduce_unique_semijoins(). This only pays when the RHS is not unique.
I think the real defect (but please correct me if I'm wrong) is that it makes a rewrite-time decision about something that should be decided on cost. I came to this conclusion late, but decided to share anyway because I believe there's a path forward.
At a high level: build a second rel; carry it through the join search; let it compete on cost. More optionality for the planner.
-----Original Message-----
From: Tom Lane <tgl@sss.pgh.pa.us>
Sent: Tuesday, August 25, 2026 8:31 PM
To: William Bernbaum <wbernbaum@dwdev.com>
Cc: pgsql-hackers@lists.postgresql.org
Subject: Re: Plan a filtering inner join as a semijoin
William Bernbaum <wbernbaum@dwdev.com> writes:
Recently I improved a dynamic SQL compiler (an ORM-like layer) using a
pattern that seems to generalize to the Postgres planner. I taught
the layer to emit an EXISTS subquery when the target relation only
served to filter, rather than fanning out a join whose extra rows were discarded.
That led me into the join elimination machinery, and to the attached
draft patch. It adds convert_joins_to_semijoins(), which recognizes
an inner join that only restricts which rows survive and adds a
JOIN_SEMI SpecialJoinInfo for the filtering relation.
I find myself a bit astonished by this proposal. Normally we try to convert semijoins to inner joins in order to gain join-order flexibility. I can't see a good reason to go in the other direction.
There might be a reason to install some special case for the query pattern you have in mind, but I really doubt that this particular special case is the best option.
regards, tom lane
Withdrawn, superseded by:
/messages/by-id/PH0PR18MB444315CD3E17255AB4A629BEA6AD2@PH0PR18MB4443.namprd18.prod.outlook.com
This patch converted a join at rewrite time. The new one builds a
second relation, carries it through the join search, and leaves the choice to
cost. It gets better plans than this one did too, in more cases.
Thanks for the review, Tom.
Will