pgsql: Reduce LEFT JOIN to ANTI JOIN using NOT NULL constraints

Reduce LEFT JOIN to ANTI JOIN using NOT NULL constraints

For a LEFT JOIN, if any var from the right-hand side (RHS) is forced
to null by upper-level quals but is known to be non-null for any
matching row, the only way the upper quals can be satisfied is if the
join fails to match, producing a null-extended row. Thus, we can
treat this left join as an anti-join.

Previously, this transformation was limited to cases where the join's
own quals were strict for the var forced to null by upper qual levels.
This patch extends the logic to check table constraints, leveraging
the NOT NULL attribute information already available thanks to the
infrastructure introduced by e2debb643. If a forced-null var belongs
to the RHS and is defined as NOT NULL in the schema (and is not
nullable due to lower-level outer joins), we know that the left join
can be reduced to an anti-join.

Note that to ensure the var is not nullable by any lower-level outer
joins within the current subtree, we collect the relids of base rels
that are nullable within each subtree during the first pass of the
reduce-outer-joins process. This allows us to verify in the second
pass that a NOT NULL var is indeed safe to treat as non-nullable.

Based on a proposal by Nicolas Adenis-Lamarre, but this is not the
original patch.

Suggested-by: Nicolas Adenis-Lamarre <nicolas(dot)adenis(dot)lamarre(at)gmail(dot)com>
Author: Tender Wang <tndrwang(at)gmail(dot)com>
Co-authored-by: Richard Guo <guofenglinux(at)gmail(dot)com>
Discussion: https://postgr.es/m/CACPGbctKMDP50PpRH09in+oWbHtZdahWSroRstLPOoSDKwoFsw@mail.gmail.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/cf74558feb8f41b2bc459f59ed3f991024d04893

Modified Files
--------------
src/backend/optimizer/prep/prepjointree.c | 204 +++++++++++++++++++++++++-----
src/test/regress/expected/join.out | 62 +++++++++
src/test/regress/sql/join.sql | 27 ++++
3 files changed, 260 insertions(+), 33 deletions(-)