Skip LEFT/ANTI joins to a provably empty inner rel

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/