Skipping NULL keys when uniqueifying a semijoin's RHS
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:t253551psql -h localhost -U postgresBuilt from patchset v3 (message #3), September 09, 2026 at 08:35 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 t253551_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 t253551_3 && git checkout t253551_3Patchset v3 (message #3) is on t253551_3
Hi hackers,
Was tinkering with semijoins in the planner and was
surprised by some cost estimates produced. Richard's
work here Fix CPU cost of right-semi and right-anti hash joins</messages/by-id/CAMbWs49XwhSC=e8_yeEaGKmKNyWR3DHH0p+e4k-bR_pgRiN8nQ@mail.gmail.com>
(db2d99323f1) fixed much but not all of what I was seeing.
Right now when the planner decides to unique-ify the RHS,
it reads every righthand row, including rows whose join key
is NULL. Those rows cannot contribute to the result. They get
sorted or hashed, deduplicated, and then discarded at the join.
The attached patch adds a pass, add_semijoin_not_null_quals(),
which runs before set_base_rel_sizes(), that walks
root->join_info_list, and, for each semijoin whose
righthand keys can be unique-ified, pushes an IS NOT NULL
restriction down onto the key.
Consider:
CREATE TABLE rhs_250000_90 AS
SELECT CASE
WHEN i % 100 < 90
THEN NULL ELSE i % 20000
END AS k,
(i % 500) AS k2
FROM generate_series(1, 250000) i;
CREATE TABLE probe AS
SELECT i AS id, (i % 500) AS id2
FROM generate_series(1, 2000) i;
ANALYZE rhs_250000_90, probe;
SELECT count(*)
FROM probe p
WHERE p.id IN (SELECT k FROM rhs_250000_90);
Master:
Aggregate
-> Hash Join
Hash Cond: (rhs_250000_90.k = p.id)
-> HashAggregate
Group Key: rhs_250000_90.k
-> Seq Scan on rhs_250000_90
-> Hash
-> Seq Scan on probe p
Patched:
Aggregate
-> Hash Right Semi Join
Hash Cond: (rhs_250000_90.k = p.id)
-> Seq Scan on rhs_250000_90
Filter: (k IS NOT NULL)
-> Hash
-> Seq Scan on probe p
Serial plans, work_mem = 64MB, best of 15/7/5 runs at 250k/1M/4M,
probe side fixed at 2000 rows. Times in ms.
shape rhs rows NULLs master patched speedup
---------------------------------------------------------
IN 250,000 0% 30.7 29.3 1.05x
IN 250,000 50% 54.8 27.2 2.01x
IN 250,000 90% 48.9 20.7 2.36x
IN 1,000,000 0% 232.8 230.6 1.01x
IN 1,000,000 50% 218.1 168.6 1.29x
IN 1,000,000 90% 203.3 94.7 2.15x
IN 4,000,000 0% 951.7 944.9 1.01x
IN 4,000,000 50% 937.5 676.4 1.39x
IN 4,000,000 90% 860.6 397.8 2.16x
IN 2-col 250,000 0% 71.6 72.4 0.99x
IN 2-col 250,000 50% 66.9 31.8 2.10x
IN 2-col 250,000 90% 63.9 22.2 2.88x
IN 2-col 1,000,000 0% 262.8 263.3 1.00x
IN 2-col 1,000,000 50% 262.2 138.4 1.89x
IN 2-col 1,000,000 90% 261.0 90.4 2.89x
IN 2-col 4,000,000 0% 1230.3 1200.9 1.02x
IN 2-col 4,000,000 50% 1168.2 548.4 2.13x
IN 2-col 4,000,000 90% 1129.1 388.3 2.91x
The cells that gain ~2x are the cells where the plan flips to a plain semi join.
The pass skips a handful of cases: NOT NULL columns known to the catalog,
entries with unknown nullability, and columns whose statistics indicate we
would gain no benefit (selectivity >= 1.0 -> no NULLs). Additionally, it prevents
double-counting selectivity when an existing strict qual already rejects.
The key also has to resolve to a single base relation, which handles outer joins for
free: pull_varnos() folds in outer-join relids, so an outer-join-nullable key
comes back with more than one id and is skipped.
A couple things worth looking at:
One of the self-join-elimination tests reorders a join. And in the lateral test,
the filter that lands on t3 is ((t1.a + a) IS NOT NULL). t1.a is an
outer reference here. Is this acceptable? pull_varnos() reports t3 alone.
Thoughts?
-Will
William Bernbaum <wbernbaum@dwdev.com> writes:
The attached patch adds a pass, add_semijoin_not_null_quals(),
which runs before set_base_rel_sizes(), that walks
root->join_info_list, and, for each semijoin whose
righthand keys can be unique-ified, pushes an IS NOT NULL
restriction down onto the key.
I'm by no means an expert on the planner, but the idea seems sound to
me, and on the surface the change looks sensible. I have just a couple
of code nitpicks:
+ ListCell *lc; + + foreach(lc, root->join_info_list) + { + SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
This should be foreach_node(SpecialJoinInfo, sjinfo, root->join_info_list).
+ ListCell *lc2;
[...]
+ foreach(lc2, sjinfo->semi_rhs_exprs) + { + Expr *expr = (Expr *) lfirst(lc2);
And this should be foreach_node(Expr, expr, sjinfo->semi_rhs_exprs).
- ilmari
Hi Ilmari,
Thanks for the review - v2 attached.
[use foreach_node for the loop over join_info_list]
Done.
[and for the loop over semi_rhs_exprs]
This one I couldn't take as written, so I used foreach_ptr
instead.
Two further changes:
First, I dropped this guard:
/* Nothing reads the whole RHS unless it can be unique-ified */
if (!sjinfo->semi_can_btree && !sjinfo->semi_can_hash)
continue;
The check was unreachable. compute_semijoin_info() assigns
sjinfo->semi_rhs_exprs only after it has already returned early on
!(all_btree || all_hash), so semi_rhs_exprs is NIL whenever both flags
are false.
Second, I added a strictness check:
/* A non-strict operator can match a NULL key */
if (!op_strict(opno))
continue;
compute_semijoin_info() requires each operator to be hashjoinable or
mergejoinable, but nothing requires it to be strict.
Thanks,
Will
On Mon, Aug 31, 2026 at 2:46 AM William Bernbaum <wbernbaum@dwdev.com> wrote:
Hi Ilmari,
Thanks for the review - v2 attached.
[use foreach_node for the loop over join_info_list]
Done.
[and for the loop over semi_rhs_exprs]
This one I couldn't take as written, so I used foreach_ptr
instead.Two further changes:
First, I dropped this guard:
/* Nothing reads the whole RHS unless it can be unique-ified */
if (!sjinfo->semi_can_btree && !sjinfo->semi_can_hash)
continue;The check was unreachable. compute_semijoin_info() assigns
sjinfo->semi_rhs_exprs only after it has already returned early on
!(all_btree || all_hash), so semi_rhs_exprs is NIL whenever both flags
are false.Second, I added a strictness check:
/* A non-strict operator can match a NULL key */
if (!op_strict(opno))
continue;compute_semijoin_info() requires each operator to be hashjoinable or
mergejoinable, but nothing requires it to be strict.Thanks,
Will
I wonder whether this work should converge with Richard Guo’s per-RelOptInfo
UniqueKey work, rather than introducing a separate notion of
deduplication eligibility.
The UniqueKey work already treats uniqueness as a planner property, much
like pathkeys do for ordering, and propagates it through joins and upper
rels. It also handles the important NULL-awareness distinction: a key
may remain useful for proving inner uniqueness even when outer joins have
made it insufficient for removing DISTINCT or GROUP BY.
/messages/by-id/CAMbWs4-iLcqBr_n_F5gNrzQbBMrKgkpGwqTu7boWeoYepf=+8g@mail.gmail.com
That seems closely related to what is needed here. An ordinary inner
join may destroy an input’s uniqueness by multiplying rows, while a
semijoin preserves the LHS uniqueness properties. Eager deduplication
can also naturally be described in terms of the uniqueness properties it
produces.
So rather than having separate machinery for UniqueKeys, eager
deduplication, and semijoin eligibility, I think it would be worth
considering whether these should converge on the same planner property
framework. That may also make future costing and transformations less
ad-hoc.
Regards
Haibo