Wrong results from an antijoin

This query gives wrong results on v16 to master:

create table t1 (a int);
create table t2 (a int primary key);
insert into t1 values (1), (10000);
insert into t2 select generate_series(1, 10000);
analyze t1, t2;

select s.* from t1 left join
(select 2 as c, t1.a as x from t1
where not exists (select 1 from t2 where t2.a = t1.a)) s on true
where s.x = s.c;
c | x
---+-------
2 | 1
2 | 1
2 | 10000
2 | 10000
(4 rows)

Note that the returned rows do not even satisfy the WHERE clause.
This scares me because it seems very easy to hit, and the result is
obviously wrong.

Nested Loop
-> Nested Loop Anti Join
-> Seq Scan on t1 t1_1
-> Index Only Scan using t2_pkey on t2
Index Cond: (a = t1_1.a)
Filter: (t1_1.a = 2)
-> Seq Scan on t1

The qual "s.x = s.c" ends up in the inner side of the antijoin, where
it does the opposite of what it should: an outer row that fails it
finds no match and gets emitted.

The cause is the PHV for s.c. When we pull up the subquery, we set
its phrels to all the relids in the subquery's jointree, and that
includes t2, the RHS of the antijoin made from the NOT EXISTS. Since
the PHV is variable-free, that is also where it is evaluated, so the
qual looks like it references t2 and is taken as a join clause movable
to a parameterized scan of t2.

Compare that with the same query written with a left join that gets
reduced to an antijoin:

select s.* from t1 left join
(select 2 as c, t1.a as x from t1
left join t2 on t1.a = t2.a where t2.a is null) s on true
where s.x = s.c;

Nested Loop
-> Nested Loop Anti Join
Filter: (t1_1.a = 2)
-> Seq Scan on t1 t1_1
-> Index Only Scan using t2_pkey on t2
Index Cond: (a = t1_1.a)
-> Seq Scan on t1

This one is correct. The antijoin has the left join's relid, which is
in phrels and so in the qual's relids, and that keeps the qual above
the join. An antijoin built by pull_up_sublinks() has rtindex 0, on
the assumption that nothing above it can reference its RHS, so there
is nothing to stop the qual.

This goes back to v16. v15 is not affected, although the PHV has the
same phrels there. In v15 check_outerjoin_delay() sees that the qual
overlaps the antijoin's RHS and puts t2 into its nullable_relids, and
join_clause_is_movable_into() then refuses to move it into t2. Both
went away in v16 along with nullable_relids, on the grounds that
clause_relids now mentions any nulling outer join. That doesn't cover
an antijoin with no relid.

We could band-aid the PHVs, by trimming the RHS of such an antijoin
from phrels or ph_eval_at (and maybe ph_lateral too). But we have
enough band-aids on PHVs already. And it's not clear to me that PHVs
are the only thing affected by an antijoin having no relid.

So I think a more principled way is to give the antijoin a relid, just
like an antijoin reduced from a left join has, so that we can leverage
the well-established outer-join relid machinery to keep quals above
it.

I'm writing a patch along these lines, but I'd like to hear what
others think before going too far.

- Richard