Hi hackers,
When the inner side of a LEFT or ANTI join is proven empty (a
constant-false ON clause, contradictory quals, or partition pruning that
removes every partition), the planner still builds a real join against
the dummy rel:
This has two costs. At execution time, the empty side is re-entered once
per outer row for nothing. The bigger issue is the row estimate. A qual
like `t.col IS NULL` pushed down to such a join gets its selectivity
from the empty rel's statistics (0.005 by default), even through it is
trivialy true for every NULL-extended row. The join is then
underestimated by orders of magnitude, and the joins above it can be
planned badly:
CREATE TABLE f (id INT, d_id INT);
INSERT INTO f SELECT i, i % 100000 FROM generate_series(1, 1000000) i;
CREATE TABLE d (id INT PRIMARY KEY, name TEXT);
INSERT INTO d SELECT i, 'n' || i FROM generate_series(0, 99999) i;
CREATE TABLE o (id INT, f_id INT, note TEXT);
ANALYZE f, d, o;
EXPLAIN ANALYZE
SELECT f.id, d.name FROM f
LEFT JOIN o ON o.f_id = f.id AND false
JOIN d ON d.id = f.d_id
WHERE o.note IS NULL;
Before patch:
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
Gather (cost=1000.29..14905.67 rows=4948 width=10) (actual
time=0.521..412.172 rows=1000000.00 loops=1)
Workers Planned: 2
Workers Launched: 2
Buffers: shared hit=2008511 read=3579
-> Nested Loop (cost=0.29..13410.87 rows=2062 width=10) (actual
time=0.187..379.346 rows=333333.33 loops=3)
Buffers: shared hit=2008511 read=3579
-> Nested Loop Left Join (cost=0.00..12758.34 rows=2083
width=8) (actual time=0.162..38.033 rows=333333.33 loops=3)
Join Filter: false
Filter: (o.note IS NULL)
Buffers: shared hit=846 read=3579
-> Parallel Seq Scan on f (cost=0.00..8591.67
rows=416667 width=8) (actual time=0.159..9.743 rows=333333.33 loops=3)
Buffers: shared hit=846 read=3579
-> Result (cost=0.00..0.00 rows=0 width=32) (actual
time=0.000..0.000 rows=0.00 loops=1000000)
Replaces: Scan on o
One-Time Filter: false
-> Index Scan using d_pkey on d (cost=0.29..0.31 rows=1
width=10) (actual time=0.001..0.001 rows=1.00 loops=1000000)
Index Cond: (id = f.d_id)
Index Searches: 1000000
Buffers: shared hit=2007665
Planning:
Buffers: shared hit=6
Planning Time: 0.199 ms
Execution Time: 424.646 ms
(23 rows)
After patch:
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
Hash Join (cost=2791.00..19841.11 rows=989550 width=10) (actual
time=18.515..139.538 rows=1000000.00 loops=1)
Hash Cond: (f.d_id = d.id)
Buffers: shared hit=635 read=4331
-> Seq Scan on f (cost=0.00..14425.00 rows=1000000 width=8)
(actual time=0.137..23.338 rows=1000000.00 loops=1)
Buffers: shared hit=94 read=4331
-> Hash (cost=1541.00..1541.00 rows=100000 width=10) (actual
time=18.331..18.331 rows=100000.00 loops=1)
Buckets: 131072 Batches: 1 Memory Usage: 5321kB
Buffers: shared hit=541
-> Seq Scan on d (cost=0.00..1541.00 rows=100000 width=10)
(actual time=0.007..6.691 rows=100000.00 loops=1)
Buffers: shared hit=541
Planning:
Buffers: shared hit=6
Planning Time: 0.190 ms
Execution Time: 149.975 ms
(14 rows)
The same happens without a literal "false", e.g. for a LEFT JOIN to a
partitioned table whose partitions are all pruned by the ON clause.
The attached patch adds try_skip_join_to_empty_rel() to
populate_joinrel_with_paths(). For JOIN_LEFT and JOIN_ANTI with a dummy
inner rel, it applies when:
- every qual pushed down to the join is "innerval IS NULL" (checked with
find_forced_null_var()), so no outer row can be filtered out;
- the join's reltarget can be computed from the outer rel alone, i.e.
pull_varnos() of the reltarget is a subset of the outer relids. As
pull_varnos() also reports nulling relids, this rejects Vars nulled by
the join itself.
In that case the join's size is set to the outer rel's, and projections
of the outer rel's unparameterized and partial paths are added as paths
for the join. The regular join paths are still generated, so the new
paths only have to win on cost. Using all of the outer paths rather than
just the cheapest one preserves sort orders (ORDER BY ... LIMIT over an
index keeps working), and the partial paths are needed so that parallel
plans don't keep the per-row nested loop.
Nothing is needed for an empty outer side: for LEFT, ANTI and SEMI joins
that already marks the whole join as dummy. RIGHT joins are covered
because they are planned as LEFT joins with the sides swapped.
FULL JOIN is deliberately not handled. There the surviving side's Vars
in the join's reltarget carry the join's nulling bit, so that side's
paths cannot emit them as is. An earlier version of this patch that
tried FULL too failed with "wrong varnullingrels" in setrefs when the
surviving side was itself a join or an Append.
--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com/
From 181c7f3c5385fff40b09968f72270a9d12062182 Mon Sep 17 00:00:00 2001
From: Evdokimov Ilia <[email protected]>
Date: Tue, 29 Sep 2026 11:21:44 +0500
Subject: [PATCH v1] Skip outer joins to a provably empty inner relation
When the inner side of a LEFT or ANTI join is proven empty (for
instance by a constant-false ON clause, contradictory restriction
quals, or partition pruning that removes every partition), we still
built a real join against the dummy rel, rescanning it once per outer
row. Worse, a qual such as "inner.x IS NULL" pushed down to the join
got its selectivity from the empty rel's statistics, although it is
trivially true for the NULL-extended rows. The join's size could thus
be underestimated by orders of magnitude, misleading the planning of
the joins above it.
If every qual pushed down to such a join is "innervar IS NULL", and
the join's targetlist can be computed from the outer rel alone, the
join returns exactly the outer rows. In that case, set the join's
size estimate to the outer rel's, and add projections of the outer
rel's unparameterized and partial paths as paths for the join. Using
all of the outer paths keeps their sort orders available, and the
partial paths let parallel plans avoid the join as well. The regular
join paths are still generated, so the new paths must win on cost.
Joins with an empty outer side need nothing new, since they are
already marked dummy as a whole. FULL JOIN is not handled: there the
surviving side's Vars in the join's targetlist are marked as nulled by
the join, so that side's paths cannot emit them as is.
---
src/backend/optimizer/path/joinrels.c | 70 +++++++++++++++++
src/test/regress/expected/join.out | 105 ++++++++++++++++++++++++++
src/test/regress/sql/join.sql | 37 +++++++++
3 files changed, 212 insertions(+)
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 10fb3e39d28..a413fcbbeca 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -16,8 +16,10 @@
#include "miscadmin.h"
#include "optimizer/appendinfo.h"
+#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/joininfo.h"
+#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planner.h"
@@ -43,6 +45,11 @@ static void make_grouped_join_rel(PlannerInfo *root, RelOptInfo *rel1,
static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
RelOptInfo *rel2, RelOptInfo *joinrel,
SpecialJoinInfo *sjinfo, List *restrictlist);
+static void try_skip_join_to_empty_rel(PlannerInfo *root,
+ RelOptInfo *joinrel,
+ RelOptInfo *outerrel,
+ RelOptInfo *innerrel,
+ List *restrictlist);
static void try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1,
RelOptInfo *rel2, RelOptInfo *joinrel,
SpecialJoinInfo *parent_sjinfo,
@@ -1145,6 +1152,9 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
if (restriction_is_constant_false(restrictlist, joinrel, false) &&
bms_is_subset(rel2->relids, sjinfo->syn_righthand))
mark_dummy_rel(rel2);
+ if (is_dummy_rel(rel2))
+ try_skip_join_to_empty_rel(root, joinrel, rel1, rel2,
+ restrictlist);
add_paths_to_joinrel(root, joinrel, rel1, rel2,
JOIN_LEFT, sjinfo,
restrictlist);
@@ -1238,6 +1248,9 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
if (restriction_is_constant_false(restrictlist, joinrel, false) &&
bms_is_subset(rel2->relids, sjinfo->syn_righthand))
mark_dummy_rel(rel2);
+ if (is_dummy_rel(rel2))
+ try_skip_join_to_empty_rel(root, joinrel, rel1, rel2,
+ restrictlist);
add_paths_to_joinrel(root, joinrel, rel1, rel2,
JOIN_ANTI, sjinfo,
restrictlist);
@@ -1613,6 +1626,63 @@ restriction_is_constant_false(List *restrictlist,
return false;
}
+/*
+ * try_skip_join_to_empty_rel
+ * A LEFT or ANTI join whose inner side is proven empty returns exactly
+ * the outer rows, so if nothing above needs the inner side we can offer
+ * the outer rel's own paths instead of a join against an empty rel.
+ *
+ * Quals pushed down to this join are evaluated on the NULL-extended rows;
+ * we only accept "innervar IS NULL", which is then trivially true (this is
+ * the usual shape, e.g. WHERE inner.x IS NULL above a LEFT JOIN).
+ */
+static void
+try_skip_join_to_empty_rel(PlannerInfo *root, RelOptInfo *joinrel,
+ RelOptInfo *outerrel, RelOptInfo *innerrel,
+ List *restrictlist)
+{
+ foreach_node(RestrictInfo, rinfo, restrictlist)
+ {
+ Var *var;
+
+ /* The join's own clauses have nothing to match */
+ if (!RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
+ continue;
+
+ var = find_forced_null_var((Node *) rinfo->clause);
+ if (var == NULL || !bms_is_member(var->varno, innerrel->relids))
+ return;
+ }
+
+ /* No outer row is filtered out, whatever the inner rel's statistics say */
+ joinrel->rows = outerrel->rows;
+
+ /*
+ * The outer rel must be able to emit the join's targetlist as is. Since
+ * pull_varnos() also reports nulling relids, this rejects both Vars of
+ * the inner rel and Vars marked as nulled by this join.
+ */
+ if (!bms_is_subset(pull_varnos(root, (Node *) joinrel->reltarget->exprs),
+ outerrel->relids))
+ return;
+
+ foreach_ptr(Path, path, outerrel->pathlist)
+ {
+ if (path->param_info == NULL)
+ add_path(joinrel, (Path *)
+ create_projection_path(root, joinrel, path,
+ joinrel->reltarget));
+ }
+
+ if (joinrel->consider_parallel)
+ {
+ foreach_ptr(Path, path, outerrel->partial_pathlist)
+ add_partial_path(joinrel, (Path *)
+ create_projection_path(root, joinrel, path,
+ joinrel->reltarget));
+ }
+}
+
/*
* Assess whether join between given two partitioned relations can be broken
* down into joins between matching partitions; a technique called
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 94e158d0dc6..fd3c36fd0f7 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -2278,6 +2278,111 @@ select aa, bb, unique1, unique1
----+----+---------+---------
(0 rows)
+--
+-- A LEFT or ANTI join to a provably empty rel need not be executed at all,
+-- if nothing above references the empty side
+--
+explain (costs off)
+select i1.f1 from int4_tbl i1 left join int4_tbl i2 on false
+ where i2.f1 is null;
+ QUERY PLAN
+-------------------------
+ Seq Scan on int4_tbl i1
+(1 row)
+
+select i1.f1 from int4_tbl i1 left join int4_tbl i2 on false
+ where i2.f1 is null;
+ f1
+-------------
+ 0
+ 123456
+ -123456
+ 2147483647
+ -2147483647
+(5 rows)
+
+-- the outer rel's sort order can still be used
+explain (costs off)
+select unique1 from tenk1 left join int4_tbl i2 on false
+ order by unique1 limit 3;
+ QUERY PLAN
+----------------------------------------------------
+ Limit
+ -> Index Only Scan using tenk1_unique1 on tenk1
+(2 rows)
+
+explain (costs off)
+select i1.f1 from int4_tbl i1
+ where not exists (select 1 from int4_tbl i2 where i2.f1 = i1.f1 and false);
+ QUERY PLAN
+-------------------------
+ Seq Scan on int4_tbl i1
+(1 row)
+
+-- the join must stay if a pushed-down qual can filter rows
+explain (costs off)
+select i1.f1 from int4_tbl i1 left join int4_tbl i2 on false
+ where coalesce(i2.f1, 0) = 1;
+ QUERY PLAN
+------------------------------------
+ Nested Loop Left Join
+ Join Filter: false
+ Filter: (COALESCE(i2.f1, 0) = 1)
+ -> Seq Scan on int4_tbl i1
+ -> Result
+ Replaces: Scan on i2
+ One-Time Filter: false
+(7 rows)
+
+select i1.f1 from int4_tbl i1 left join int4_tbl i2 on false
+ where coalesce(i2.f1, 0) = 1;
+ f1
+----
+(0 rows)
+
+-- ... or if the empty side's columns are needed
+explain (costs off)
+select * from int4_tbl i1 left join int4_tbl i2 on false;
+ QUERY PLAN
+--------------------------------
+ Nested Loop Left Join
+ Join Filter: false
+ -> Seq Scan on int4_tbl i1
+ -> Result
+ Replaces: Scan on i2
+ One-Time Filter: false
+(6 rows)
+
+-- no such shortcut for FULL JOIN, whose outputs are nulled by the join
+explain (costs off)
+select a.f1 from (int4_tbl a join int4_tbl b on a.f1 = b.f1)
+ full join (select * from int4_tbl where false) s on a.f1 = s.f1;
+ QUERY PLAN
+------------------------------------------
+ Hash Full Join
+ Hash Cond: (a.f1 = int4_tbl.f1)
+ -> Hash Join
+ Hash Cond: (a.f1 = b.f1)
+ -> Seq Scan on int4_tbl a
+ -> Hash
+ -> Seq Scan on int4_tbl b
+ -> Hash
+ -> Result
+ Replaces: Scan on int4_tbl
+ One-Time Filter: false
+(11 rows)
+
+select a.f1 from (int4_tbl a join int4_tbl b on a.f1 = b.f1)
+ full join (select * from int4_tbl where false) s on a.f1 = s.f1;
+ f1
+-------------
+ 0
+ 123456
+ -123456
+ 2147483647
+ -2147483647
+(5 rows)
+
--
-- regression test: check handling of empty-FROM subquery underneath outer join
--
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 576a90dfc1b..f903b113e7a 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -398,6 +398,43 @@ select aa, bb, unique1, unique1
from tenk1 right join b_star on aa = unique1
where bb < bb and bb is null;
+--
+-- A LEFT or ANTI join to a provably empty rel need not be executed at all,
+-- if nothing above references the empty side
+--
+explain (costs off)
+select i1.f1 from int4_tbl i1 left join int4_tbl i2 on false
+ where i2.f1 is null;
+select i1.f1 from int4_tbl i1 left join int4_tbl i2 on false
+ where i2.f1 is null;
+
+-- the outer rel's sort order can still be used
+explain (costs off)
+select unique1 from tenk1 left join int4_tbl i2 on false
+ order by unique1 limit 3;
+
+explain (costs off)
+select i1.f1 from int4_tbl i1
+ where not exists (select 1 from int4_tbl i2 where i2.f1 = i1.f1 and false);
+
+-- the join must stay if a pushed-down qual can filter rows
+explain (costs off)
+select i1.f1 from int4_tbl i1 left join int4_tbl i2 on false
+ where coalesce(i2.f1, 0) = 1;
+select i1.f1 from int4_tbl i1 left join int4_tbl i2 on false
+ where coalesce(i2.f1, 0) = 1;
+
+-- ... or if the empty side's columns are needed
+explain (costs off)
+select * from int4_tbl i1 left join int4_tbl i2 on false;
+
+-- no such shortcut for FULL JOIN, whose outputs are nulled by the join
+explain (costs off)
+select a.f1 from (int4_tbl a join int4_tbl b on a.f1 = b.f1)
+ full join (select * from int4_tbl where false) s on a.f1 = s.f1;
+select a.f1 from (int4_tbl a join int4_tbl b on a.f1 = b.f1)
+ full join (select * from int4_tbl where false) s on a.f1 = s.f1;
+
--
-- regression test: check handling of empty-FROM subquery underneath outer join
--
--
2.43.0
