Skip LEFT/ANTI joins to a provably empty inner rel - Mailing list pgsql-hackers

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/