Skipping NULL keys when uniqueifying a semijoin's RHS

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<https://www.postgresql.org/message-id/CAMbWs49XwhSC%3De8_yeEaGKmKNyWR3DHH0p%2Be4k-bR_pgRiN8nQ%40mail.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