Performance regression caused by SubLink pull-up

In [1] it was reported that pulling up a SubLink in the query below
causes a severe performance regression.

select * from t1 where exists
(select 1 from t2 where t2.a in
(select t3.a from t3 where t3.b = t1.b));

I tested it with the data from the report. If we do not pull up the
outer SubLink, the Execution Time: 6.020 ms. If we do, as master
does, the Execution Time: 3380.646 ms.

So I think this is more than a missed optimization; it is an active
pessimization.

I had a look into this issue, and here is what I found.

Pulling up the outer SubLink takes away the inner one's own chance to
be pulled up. While the inner SubLink sits inside the subquery, the
outer query's rels are a level further up, so only t2 need be in
available_rels, and it converts to a semijoin there. Once the outer
SubLink is pulled up, the inner one lands in the top-level qual
referencing both t1 and t2; pull_up_sublinks_qual_recurse has just two
places to put a new join, the semijoin's LHS and its RHS, and a
SubLink referencing both fits neither. So it stays a SubPlan, and the
join it used to get is gone.

If we do not pull up the outer SubLink, the plan is in form:

Form 1: A WHERE EXISTS SubPlan[ B SEMI JOIN C ON P ]

Write a=|A|, b=|B|, c=|C|, and P = Pbc AND Pabc, where Pbc references
only B and/or C, whereas Pabc also references A.

Since there is a valid Pbc, the cost of Form 1 is:

Cost1 = O(a*(b+c)) B and C joined, once per A row

If we pull up the outer sublink, as master does, the plan is in form:

Form 2: A SEMI JOIN B ON SubPlan[C]

With beta(x) the position of the first qualifying B row and N = sum of
beta(x) <= a*b the number of pairs reached:

hashed SubPlan: c + N built once, O(1) per probe
rescanned SubPlan: N*s s in [1,c]

In the reported case the SubPlan is not hashable, so the cost is:

Cost2 = O(a*b*c)

and it really does reach that: the SubPlan is executed 990055 times.

Regarding the fix, I think one way is to teach the planner to pull up
sublinks that reference both sides of a new semijoin.

Before:

SELECT * FROM A WHERE EXISTS
(SELECT 1 FROM B WHERE EXISTS (SELECT 1 FROM C WHERE P));

After:

SELECT * FROM A WHERE EXISTS
(SELECT 1 FROM B, C WHERE P);

The first asks: is there a B row for which some C row satisfies P?

The second asks: is there a (B, C) pair satisfying P?

So they ask the same question.

Duplicates can't matter because we're deciding whether to emit rows of
A, not of B or C. How many pairs qualify is invisible in the output.

However, this transformation is not always a win. If there is no join
condition between B and C, the B/C join is a cross product, which can
be worse than the SubPlan it displaces, especially when that SubPlan
can be hashed. So I'm thinking we do this only when Pbc actually
relates B to C, in which case we get this form:

Form 3: A SEMI JOIN (B JOIN C ON Pbc) ON Pabc

Write R = |B JOIN C ON Pbc|, then the cost is:

W = producing the join. At least R, since those rows must be
emitted; b + c + R for a hash join, which is what a hashable
Pbc gives.
Cost3 = W + a Pabc gives a clean A | {B,C} split, so the RHS
is built once and probed a times

R can be as small as O(b), when the C side of Pbc is key-like, and as
large as b*c when it is not, on the data alone. In the first case
Cost3 = O(a+b+c).

Which end R falls at depends on the selectivity of Pbc, and that isn't
knowable this early, so the test is a heuristic.

I ran this with the same data, and the Execution Time: 0.605 ms.

Attached is the patch implementing this. Any thoughts?

[1] https://postgr.es/m/13beb150.7b23.19fb3cf6efc.Coremail.ld_zju@126.com

- Richard